跳转至

面试题 17.22. 单词转换

题目描述

给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。

编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:
["hit","hot","dot","lot","log","cog"]

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

解法

方法一：DFS

我们定义一个答案数组 $\textit{ans}$，初始时只包含 $\textit{beginWord}$。然后我们定义一个数组 $\textit{vis}$，用来标记 $\textit{wordList}$ 中的单词是否被访问过。

接下来，我们设计一个函数 $\text{dfs}(s)$，表示从 $\textit{s}$ 出发，尝试将 $\textit{s}$ 转换为 $\textit{endWord}$，是否能够成功。如果能够成功，返回 $\text{True}$，否则返回 $\text{False}$。

函数 $\text{dfs}(s)$ 的具体实现如下：

  1. 如果 $\textit{s}$ 等于 $\textit{endWord}$，说明转换成功，返回 $\text{True}$；
  2. 否则，我们遍历 $\textit{wordList}$ 中的每个单词 $\textit{t}$，如果 $\textit{t}$ 没有被访问过且 $\textit{s}$ 和 $\textit{t}$ 之间只有一个字符不同，那么我们将 $\textit{t}$ 标记为已访问，并将 $\textit{t}$ 加入到 $\textit{ans}$ 中，然后递归调用 $\text{dfs}(t)$，如果返回 $\text{True}$，说明转换成功，我们返回 $\text{True}$，否则我们将 $\textit{t}$ 从 $\textit{ans}$ 中移除，继续遍历下一个单词；
  3. 如果遍历完 $\textit{wordList}$ 中的所有单词都没有找到可以转换的单词，说明转换失败，我们返回 $\text{False}$。

最后，我们调用 $\text{dfs}(\textit{beginWord})$，如果返回 $\text{True}$，说明转换成功，我们返回 $\textit{ans}$，否则返回空数组。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def findLadders(
        self, beginWord: str, endWord: str, wordList: List[str]
    ) -> List[str]:
        def check(s: str, t: str) -> bool:
            return len(s) == len(t) and sum(a != b for a, b in zip(s, t)) == 1

        def dfs(s: str) -> bool:
            if s == endWord:
                return True
            for i, t in enumerate(wordList):
                if not vis[i] and check(s, t):
                    vis[i] = True
                    ans.append(t)
                    if dfs(t):
                        return True
                    ans.pop()
            return False

        ans = [beginWord]
        vis = [False] * len(wordList)
        return ans if dfs(beginWord) else []

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    private List<String> ans = new ArrayList<>();
    private List<String> wordList;
    private String endWord;
    private boolean[] vis;

    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        this.wordList = wordList;
        this.endWord = endWord;
        ans.add(beginWord);
        vis = new boolean[wordList.size()];
        return dfs(beginWord) ? ans : List.of();
    }

    private boolean dfs(String s) {
        if (s.equals(endWord)) {
            return true;
        }
        for (int i = 0; i < wordList.size(); ++i) {
            String t = wordList.get(i);
            if (vis[i] || !check(s, t)) {
                continue;
            }
            vis[i] = true;
            ans.add(t);
            if (dfs(t)) {
                return true;
            }
            ans.remove(ans.size() - 1);
        }
        return false;
    }

    private boolean check(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) != t.charAt(i)) {
                ++cnt;
            }
        }
        return cnt == 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    vector<string> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        this->endWord = move(endWord);
        this->wordList = move(wordList);
        vis.resize(this->wordList.size(), false);
        ans.push_back(beginWord);
        if (dfs(beginWord)) {
            return ans;
        }
        return {};
    }

private:
    vector<string> ans;
    vector<bool> vis;
    string endWord;
    vector<string> wordList;

    bool check(string& s, string& t) {
        if (s.size() != t.size()) {
            return false;
        }
        int cnt = 0;
        for (int i = 0; i < s.size(); ++i) {
            cnt += s[i] != t[i];
        }
        return cnt == 1;
    }

    bool dfs(string& s) {
        if (s == endWord) {
            return true;
        }
        for (int i = 0; i < wordList.size(); ++i) {
            string& t = wordList[i];
            if (!vis[i] && check(s, t)) {
                vis[i] = true;
                ans.push_back(t);
                if (dfs(t)) {
                    return true;
                }
                ans.pop_back();
            }
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func findLadders(beginWord string, endWord string, wordList []string) []string {
    ans := []string{beginWord}
    vis := make([]bool, len(wordList))
    check := func(s, t string) bool {
        if len(s) != len(t) {
            return false
        }
        cnt := 0
        for i := range s {
            if s[i] != t[i] {
                cnt++
            }
        }
        return cnt == 1
    }
    var dfs func(s string) bool
    dfs = func(s string) bool {
        if s == endWord {
            return true
        }
        for i, t := range wordList {
            if !vis[i] && check(s, t) {
                vis[i] = true
                ans = append(ans, t)
                if dfs(t) {
                    return true
                }
                ans = ans[:len(ans)-1]
            }
        }
        return false
    }
    if dfs(beginWord) {
        return ans
    }
    return []string{}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function findLadders(beginWord: string, endWord: string, wordList: string[]): string[] {
    const ans: string[] = [beginWord];
    const vis: boolean[] = Array(wordList.length).fill(false);
    const check = (s: string, t: string): boolean => {
        if (s.length !== t.length) {
            return false;
        }
        let cnt = 0;
        for (let i = 0; i < s.length; ++i) {
            if (s[i] !== t[i]) {
                ++cnt;
            }
        }
        return cnt === 1;
    };
    const dfs = (s: string): boolean => {
        if (s === endWord) {
            return true;
        }
        for (let i = 0; i < wordList.length; ++i) {
            const t: string = wordList[i];
            if (!vis[i] && check(s, t)) {
                vis[i] = true;
                ans.push(t);
                if (dfs(t)) {
                    return true;
                }
                ans.pop();
            }
        }
        return false;
    };
    return dfs(beginWord) ? ans : [];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    private var ans: [String] = []
    private var wordList: [String] = []
    private var endWord: String = ""
    private var vis: [Bool] = []

    func findLadders(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> [String] {
        self.wordList = wordList
        self.endWord = endWord
        ans.append(beginWord)
        vis = Array(repeating: false, count: wordList.count)
        return dfs(beginWord) ? ans : []
    }

    private func dfs(_ s: String) -> Bool {
        if s == endWord {
            return true
        }
        for i in 0..<wordList.count {
            let t = wordList[i]
            if vis[i] || !check(s, t) {
                continue
            }
            vis[i] = true
            ans.append(t)
            if dfs(t) {
                return true
            }
            ans.removeLast()
        }
        return false
    }

    private func check(_ s: String, _ t: String) -> Bool {
        if s.count != t.count {
            return false
        }
        var cnt = 0
        for (sc, tc) in zip(s, t) {
            if sc != tc {
                cnt += 1
                if cnt > 1 {
                    return false
                }
            }
        }
        return cnt == 1
    }
}

评论