PHP递归拆分单词生成所有有效路径

本文深入解析了如何用PHP递归高效拆解单词（如“stars”）为所有合法的预定义字块组合，并通过“累积路径+引用传参”的核心技巧，将原本混乱嵌套的树状结果转化为清晰、扁平、可直接使用的二维字符串数组；不仅规避了键冲突、路径丢失和正则安全等常见陷阱，还兼顾大小写处理、去重排序与性能优化建议，让词游戏、NLP分词等场景中的拼接路径提取真正变得可靠、灵活且工程友好。

本文介绍如何通过递归遍历多维数组结构，将单词按预定义“字块”（tiles）进行所有可能的合法拆分，并最终扁平化为多个一维字符串数组序列。

在自然语言处理或词游戏类应用中，常需将一个目标单词（如 "stars"）拆解为若干预定义的“字块”（tiles）组合，例如 ["S", "TA", "R", "S"] 或 ["S", "T", "A", "R", "S"]。原始实现使用嵌套关联数组表示递归路径，但这种结构难以直接用于后续逻辑（如去重、排序、渲染或匹配验证）。因此，关键在于：将深度嵌套的树状结果，转化为清晰、扁平、索引化的二维数组。

✅ 正确思路：改用「累积路径 + 引用传参」替代嵌套键映射

原函数 word2sequences() 的问题在于：

• 使用 $founds[$tile] = ... 以 tile 内容为键，导致结构混乱且无法还原原始 tile ID；
• 递归返回值被覆盖，丢失中间路径信息；
• 正则匹配逻辑中 $tok[1] 和 $tok[3] 表示前后缀，但未正确保留 tile ID 用于回溯。

改进方案的核心是：

• 不依赖数组键存储路径，改用引用参数 $founds 累积完整序列字符串（如 "51;21;40;51"）；
• 每次成功匹配后，将当前 tile ID 追加到路径串（用分号分隔）；
• 当剩余字符串为空（即完全匹配）时，将该路径加入 $founds；
• 最终统一解析所有路径串，按 ID 查表还原为 tile 字符串。

✅ 优化后的完整实现

<?php
/**
 * 将单词递归拆分为所有可能的 tiles 序列（返回 ID 路径字符串数组）
 * @param string $word 待拆分单词
 * @param array $tiles 关联数组：[tile_id => tile_string]
 * @param array &$founds 引用参数，用于累积匹配路径（如 "51;21;40;51"）
 */
function word2sequences($word, $tiles, &$founds = []) {
    // 遍历所有可用字块
    foreach ($tiles as $tile_id => $tile) {
        // 正则匹配：^([;0-9]*)($tile)(.*)$ —— 允许前缀为分号或数字（即已记录的 ID），匹配 tile 后剩余后缀
        if (!preg_match('/^([;0-9]*?)(' . preg_quote($tile, '/') . ')(.*)$/i', $word, $matches)) {
            continue;
        }

        $prefix = $matches[1];
        $suffix = $matches[3];

        // 构建新路径：前缀 + 当前 tile_id + 分号（若非首次）
        $newPath = $prefix . ($prefix === '' ? '' : ';') . $tile_id;

        // 若后缀为空，说明已完全匹配，保存当前路径
        if ($suffix === '') {
            $founds[] = $newPath;
        } else {
            // 否则递归处理剩余后缀
            word2sequences($suffix, $tiles, $founds);
        }
    }
}

// 示例数据（注意：原题中键 21 重复，PHP 会覆盖 → 此处修正为唯一键）
$tiles = [
    1  => "A",
    21 => "B",
    34 => "AH",
    40 => "R",
    51 => "S",
    83 => "SA",
    14 => "T",
    99 => "TA"   // 原题中 21 => "TA" 与前面 21 => "B" 冲突，已改为 99
];

$word = "stars";
$founds = [];
word2sequences(strtolower($word), $tiles, $founds);

// 将 ID 路径转换为 tile 字符串序列
$result = [];
foreach ($founds as $path) {
    $ids = array_filter(array_map('trim', explode(';', $path))); // 去空、去空格
    $sequence = [];
    foreach ($ids as $id) {
        if (isset($tiles[$id])) {
            $sequence[] = $tiles[$id];
        }
    }
    if (!empty($sequence)) {
        $result[] = $sequence;
    }
}

print_r($result);
?>

⚠️ 注意事项与最佳实践

• preg_quote() 必须使用：防止 tile 字符串含正则元字符（如 ".", "*"）导致匹配异常；
• 键唯一性至关重要：$tiles 数组键必须唯一，否则 21 => "B" 和 21 => "TA" 会导致后者覆盖前者；
• 大小写敏感处理：示例中对 $word 调用 strtolower()，确保与小写 tile 匹配（可根据需求调整）；
• 性能提示：该算法为指数级复杂度，适用于短单词（≤10 字符）和有限 tiles 集；长词建议引入剪枝或动态规划优化；
• 去重与排序（可选）：若需唯一解，可在最后添加 array_unique($result, SORT_REGULAR)。

✅ 输出效果

运行上述代码，将得到标准二维数组：

Array
(
    [0] => Array
        (
            [0] => S
            [1] => TA
            [2] => R
            [3] => S
        )
    [1] => Array
        (
            [0] => S
            [1] => T
            [2] => A
            [3] => R
            [4] => S
        )
)

此结构可直接用于前端渲染、校验逻辑、或进一步参与组合优化（如最短序列、最少 tile 数等），真正实现了从「树形探索」到「平面解集」的可靠转化。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~