关于算法:搜索算法系列-双向搜索

字串变换问题

已知两个字串 a、b，两个数组 from、to，变换规定为：from[i]能够转换为 to[i]。问 a 到 b 须要通过多少次变换？若 10 步内 a 无奈变换到 b，输入 ’NO ANSWER!’。

例如对于 a = 'abcd'，b = 'xyz'，from = ['abc', 'ud', 'y']，to = ['xu', 'y', 'yz']：'abcd' -> 'xud' -> 'xy' -> 'xyz' 须要经验 3 次变换。

该题的解决方案应用到了广度优先搜寻，咱们将通过一次变换可能失去的所有字符串作为一种状态，而后判断是否存在指标字符串，不存在则计算下一层状态，存在则以后层数为最小变换次数。

能够失去如下代码。

def solution(a, b, f, t):
    def extend(h, q):
        s, n = h
        for i in range(len(s)):
            for j in range(len(f)):
                if f[j] != s[i:i+len(f[j])]:
                    continue
                q.append([s[:i] + t[j] + s[i+len(f[j]):], n+1])
    queue = [[a, 0]]
    while queue:
        head = queue.pop(0)
        if head[0] == b: return head[1]
        extend(head, queue)
    return 'NO ANSWER!'

如果该题目没有工夫限度，这样写当然没有问题。

思考一个字符串的一次变换的所有可能，与字符串的长度和变换规定无关，这个中间状态可能数量十分宏大，那咱们如何对该代码进行优化呢？

如果你浏览过我的上一篇文章可能会想到通过拆分问题规模来别离求解，以达到升高问题数量级的目标。而在本题中，咱们别离从 a 和 b 同时开始搜寻，如果它们的搜寻门路相遇了，即找到最小变换次数，通过双向搜寻的形式，咱们将规模为 2N 的问题，合成为了两个规模为 N 的问题。

def solution(a, b, f, t):
    ans = float('inf')
    qa, qb, da, db = [a], [b], {a:0}, {b:0}
    level = 0

    def extend(q, d, f, t):
        s = q.pop(0)
        for i in range(len(s)):
            for j in range(len(f)):
                if f[j] != s[i:i+len(f[j])]:
                    continue
                tmp = s[:i] + t[j] + s[i+len(f[j]):]
                q.append(tmp)
                d[tmp] = d[s]+1

    while qa and qb and level <= 10:
        while qa and da[qa[0]] == level:
            extend(qa, da, f, t)
        while qb and db[qb[0]] == level:
            extend(qb, db, t, f)
        level += 1
        for k in da.keys():
            ans = min(ans, da[k] + db.get(k, float('inf')))
        if ans < float('inf'): return ans
    return 'NO ANSWER!'

该段代码中，开拓了两个队列和两个字典，别离存储双向搜寻状态和字串所在层数。每一次队列扩大整一层的数据，用 level 来记录以后层数。扩大实现后判断两个字典是否有公共键值，如果有则阐明发现了搜寻门路的交点，对应层数相加即转换次数。

本文示例题目与 acwing 190. 字串变换统一，读者可自行尝试提交，验证本人代码的正确性。