Word Ladder

update Jul 21, 2017 16:45

LintCode

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

• Only one letter can be changed at a time

• Each intermediate word must exist in the dictionary

  Notice

• Return 0 if there is no such transformation sequence.

• All words have the same length.

• All words contain only lowercase alphabetic characters.

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Basic Idea:

这道题目其实是一个隐式图搜索的题目，要求的是最短的变化路径长度，所以首选BFS。 如上就是这个图的例子（来自jiuzhang）。 实现的基本思路就是每次考虑距离当前word只有一个编辑距离的dict中的词，如果还没有visit过，则加入queue，分层bfs，记录step数。 细节: 在生成 1 编辑距离的neighbors时，如果对所有dict中的单词逐一检查，是O(#words in dict * length) 的时间复杂度，所以这里采用生成所有 1 编辑距离的变化的单词，然后查看dict中是否有这个词，是O(26 * length^2)的复杂度，在dict中word很多而长度较短的时候，更有优势。

python code:

    class Solution:
        # @param start, a string
        # @param end, a string
        # @param dict, a set of string
        # @return an integer
        def __init__(self):
            self.visited = set()

        def ladderLength(self, start, end, dict):
            if start == end:
                return 1
            dict.add(end)

            # bfs
            queue = collections.deque()
            queue.appendleft(start)
            step = 1
            while queue:
                size = len(queue)
                step += 1
                for i in range(size):
                    node = queue.pop()
                    for neighbor in self.getNeighbors(node, dict):
                        if neighbor == end: return step
                        queue.appendleft(neighbor)
                        self.visited.add(neighbor)
            return 0

        def replace(self, str, index, c):
            lst = list(str)
            lst[index] = c
            return ''.join(lst)

        def getNeighbors(self, str, dict):
            ret = []
            for i in range(len(str)):
                for c in range(ord('a'), ord('z') + 1):
                    neighbor = self.replace(str, i, chr(c))
                    if neighbor in dict:
                        if neighbor in self.visited:
                            continue
                        ret.append(neighbor)
            return ret

java code:

    public class Solution {
        /**
          * @param start, a string
          * @param end, a string
          * @param dict, a set of string
          * @return an integer
          */
        private Set<String> visited;

        public int ladderLength(String start, String end, Set<String> dict) {
            if (start.equals(end)) return 1;
            dict.add(end); // 先把end加入dict，否则无法直接判断终点
            visited = new HashSet<String>();
            Deque<String> queue = new LinkedList<>();
            queue.addFirst(start);
            int step = 1;
            while (! queue.isEmpty()) {
                int size = queue.size();
                step++;
                for (int i = 0; i < size; ++i) {
                    String node = queue.removeLast();
                    for (String neighbor : getNeighbors(node, dict)) {
                        // 无需判断是否在visited中，因为getNeighbors已经判断过了
                        if (neighbor.equals(end)) return step;
                        queue.addFirst(neighbor);
                        visited.add(neighbor);
                    }
                }
            }
            return 0;
        }

        private String replace(String str, int index, char c) {
            char[] arr = str.toCharArray();
            arr[index] = c;
            return String.valueOf(arr);
        }

        private List<String> getNeighbors(String node, Set<String> dict) {
            List<String> ret = new ArrayList<>();
            for (int i = 0; i < node.length(); ++i) {
                for (int c = 'a'; c <= 'z'; ++c) {
                    String str = replace(node, i, (char)c);
                    if (dict.contains(str)) {
                        if (! visited.contains(str)) {
                            ret.add(str);
                        }
                    }
                }
            }
            return ret;
        }
    }

update 2018-06-23 22:07:35

Update C++ BFS Solution

class Solution {
public:
    int ladderLength(string &start, string &end, unordered_set<string> &dict) {
        if (start == end) return 1;
        dict.insert(start);
        dict.insert(end);
        deque<string> q;
        q.push_back(start);
        unordered_set<string> visited;
        visited.insert(start);
        int step = 1;
        while (! q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                string curr = q.front(); q.pop_front();
                vector<string> nextWords;
                getNextWord(curr, dict, nextWords);
                for (string nextWord : nextWords) {
                    // visit 当前word，检查其是否已经visited，如果不是，将其加入visited set
                    if (! visited.insert(nextWord).second) continue;
                    if (nextWord == end) return step + 1;
                    q.push_back(nextWord);
                }
            }
            ++step;
        }
        return -1;
    }
private:
    void getNextWord(const string& curr, const unordered_set<string>& dict, vector<string>& res) {
        for (int i = 0; i < curr.size(); ++i) {
            for (int j = 0; j < 25; ++j) {
                string s = curr;
                s[i] = 'a' + j;
                if (s != curr && dict.count(s)) {
                    res.push_back(s);
                }
            }
        }
    }
};

update Sep 9, 2019

Update, Leetcode version

Leetcode 上的版本和lintcode有些许出入，但只需要略加修改即可：

Java Code:

public class Solution {

    private Set<String> visited;

    public int ladderLength(String start, String end, List<String> wordList) {
        if (start.equals(end)) return 1;
        Set<String> dict = new HashSet<>(wordList);
        // dict.add(end); // 先把end加入dict，否则无法直接判断终点

        // problem changed, now, instead adding end into dict, we need to check if end is in dict first
        if (!dict.contains(end)) return 0;

        visited = new HashSet<String>();
        Deque<String> queue = new LinkedList<>();
        queue.addFirst(start);
        int step = 1;
        while (! queue.isEmpty()) {
            int size = queue.size();
            step++;
            for (int i = 0; i < size; ++i) {
                String node = queue.removeLast();
                for (String neighbor : getNeighbors(node, dict)) {
                    // 无需判断是否在visited中，因为getNeighbors已经判断过了
                    if (neighbor.equals(end)) return step;
                    queue.addFirst(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        return 0;
    }

    private String replace(String str, int index, char c) {
        char[] arr = str.toCharArray();
        arr[index] = c;
        return String.valueOf(arr);
    }

    private List<String> getNeighbors(String node, Set<String> dict) {
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < node.length(); ++i) {
            for (int c = 'a'; c <= 'z'; ++c) {
                String str = replace(node, i, (char)c);
                if (dict.contains(str)) {
                    if (! visited.contains(str)) {
                        ret.add(str);
                    }
                }
            }
        }
        return ret;
    }
}

C++ Code

有一点可以优化的地方，其实我们不需要另外使用一个 visited set，而是可以利用 wordSet（dict），每当我们将一个neighbor放入queue，我们就在wordset中将其去掉。

class Solution {
  public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        deque<string> queue{beginWord};

        if (!wordSet.count(endWord)) return 0;

        int level = 0;
        while (!queue.empty()) {
            level++;
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                string word = std::move(queue.back());
                if (word == endWord) return level;
                queue.pop_back();
                auto neighbors = getNeighbors(word, wordSet);
                queue.insert(queue.begin(), neighbors.begin(), neighbors.end());
            }
        }
        return 0;
    }
  private:
    vector<string> getNeighbors(string& word, unordered_set<string>& wordSet) {
        vector<string> ret;
        for (int i = 0; i < word.size(); ++i) {
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c != word[i]) {
                    string tmp = word;
                    tmp[i] = c;
                    if (wordSet.count(tmp)) {
                        // std::cout << neighbor << std::endl;
                        wordSet.erase(tmp); // 在wordSet中去掉，相当于标记为visited
                        ret.push_back(std::move(tmp));
                    }
                }
            }
        }
        return ret;
    }
};