LeetCode 127 Word Ladder

概述

https://leetcode.com/problems/word-ladder/

动态规划法 + 回溯

实现的时候注意：

1. 让求得是字梯的长度，不是转换的次数，需要 + 1；
2. endWord 可能不存在；

有 bug 的解法（44 / 50 test cases passed）：

class Solution {
public:
    unordered_map<string, int> m;
    int ladderLength(string& beginWord, string& endWord, vector<string>& wordList) {
        bool existed = false;
        for (auto& w : wordList) {
            if (w == endWord) {
                existed = true;
                break;
            }
        }
        if (!existed) return 0;
        vector<bool> used(wordList.size(), false);
        int ans = helper(beginWord, endWord, wordList, used);
        if (ans == INT_MAX) return 0;
        else return ans + 1;
    }
    
    int helper(string& beginWord, string& endWord, vector<string>& wordList, vector<bool>& used) {
        // if (beginWord == endWord) return 0;
        if (isValid(beginWord, endWord)) return 1;
        if (m.count(beginWord)) return m[beginWord];
        int ans = INT_MAX;
        for (int i = 0; i < wordList.size(); i ++) {
            if (used[i] || wordList[i] == beginWord) continue;
            if (isValid(beginWord, wordList[i])) {
                used[i] = true;
                int future = helper(wordList[i], endWord, wordList, used);
                // cout << beginWord << " choose " << wordList[i] << " future " << future << endl;
                used[i] = false;
                if (future != INT_MAX) {
                    ans = min(ans, 1 + future);
                }
            }
        }
        m[beginWord] = ans;
        return ans;
    }
    
    bool isValid(string& a, string& b) {
        if (a.size() != b.size()) return false;
        bool used = false;
        for (int i = 0; i < a.size(); i ++) {
            if (a[i] == b[i]) continue;
            if (used) return false;
            used = true;
        }
        return used;
    }
};

宽度优先搜索

https://leetcode.com/problems/word-ladder/discuss/40707/C%2B%2B-BFS

TLE 了（34 / 50 test cases passed）：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<string> todo;
        todo.push(beginWord);
        int ladder = 1;
        while (!todo.empty()) {
            int sz = todo.size();
            while (sz--) {
                auto c = todo.front(); todo.pop();
                if (c == endWord) return ladder;
                dict.erase(c);
                for (auto iter = dict.begin(); iter != dict.end(); iter ++) {
                    if (isValid(c, *iter)) {
                        todo.push(*iter);
                    }
                }
            }
            ladder ++;
        }
        return 0;
    }
    
    bool isValid(string& a, string b) {
        if (a.size() != b.size()) return false;
        bool used = false;
        for (int i = 0; i < a.size(); i ++) {
            if (a[i] == b[i]) continue;
            if (used) return false;
            used = true;
        }
        return used;
    }    
};

当字典很长时，遍历字典不如遍历一个单词的所有可能组成方式（起码是常量，虽然大了点）：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<string> todo;
        todo.push(beginWord);
        int ladder = 1;
        while (!todo.empty()) {
            int sz = todo.size();
            while (sz--) {
                auto word = todo.front(); todo.pop();
                if (word == endWord) return ladder;
                dict.erase(word);
                for (int i = 0; i < word.size(); i ++) {
                    char c = word[i];
                    for (int j = 0; j < 26; j ++) {
                        word[i] = 'a' + j;
                        if (dict.count(word)) todo.push(word);
                    }
                    word[i] = c;
                }
            }
            ladder ++;
        }
        return 0;
    }   
};

然而还是 TLE 了：50 / 50 test cases passed, but took too long.

注意哦，上面的实现中，我们可能会 erase 一个 key 多次，但是没关系，erase 可以处理不存在的 key， 实际上其返回了一个值用来指示 erase 了多少 key。

不慌，这个时候我们只需要冷静分析再提交一次就好了，AC 了哦耶。

Links: leetcode-127-word-ladder

未经允许，禁止转载，本文源站链接：https://iamazing.cn/