字母游戏问题？

Question

最近在一次面试中，我遇到了以下问题：

1. 写一个可以在命令行运行的脚本，使用python。

2. 这个脚本应该能够接收两个单词作为命令行输入（或者你也可以选择让用户通过控制台输入这两个单词）。

3. 给定这两个单词： a. 确保它们的长度相同 b. 确保它们都是你下载的有效英语单词字典中的单词。

4. 如果满足条件，计算是否可以通过以下步骤从第一个单词到达第二个单词： a. 每次只能改变一个字母 b. 每次改变字母后，得到的新单词也必须在字典中存在 c. 不能添加或删除字母。

5. 如果这两个单词可以互相到达，脚本应该打印出从一个单词到另一个单词的最短路径。

6. 你可以使用/usr/share/dict/words作为你的单词字典。

我的解决方案是使用广度优先搜索来找到两个单词之间的最短路径。但显然这并不足以让我得到这份工作 :(

你们知道我可能哪里做错了吗？非常感谢。

import collections
import functools
import re

def time_func(func):
    import time

    def wrapper(*args, **kwargs):
        start = time.time()
        res = func(*args, **kwargs)
        timed = time.time() - start

        setattr(wrapper, 'time_taken', timed)
        return res

    functools.update_wrapper(wrapper, func)
    return wrapper

class OneLetterGame:
    def __init__(self, dict_path):
        self.dict_path = dict_path
        self.words = set()

    def run(self, start_word, end_word):
        '''Runs the one letter game with the given start and end words.
        '''
        assert len(start_word) == len(end_word), \
            'Start word and end word must of the same length.'

        self.read_dict(len(start_word))

        path = self.shortest_path(start_word, end_word)
        if not path:
            print 'There is no path between %s and %s (took %.2f sec.)' % (
                start_word, end_word, find_shortest_path.time_taken)
        else:
            print 'The shortest path (found in %.2f sec.) is:\n=> %s' % (
                self.shortest_path.time_taken, ' -- '.join(path))

    def _bfs(self, start):
        '''Implementation of breadth first search as a generator.

        The portion of the graph to explore is given on demand using get_neighboors.
        Care was taken so that a vertex / node is explored only once.
        '''
        queue = collections.deque([(None, start)])
        inqueue = set([start])

        while queue:
            parent, node = queue.popleft()
            yield parent, node

            new = set(self.get_neighbours(node)) - inqueue
            inqueue = inqueue | new
            queue.extend([(node, child) for child in new])

    @time_func
    def shortest_path(self, start, end):
        '''Returns the shortest path from start to end using bfs.
        '''
        assert start in self.words, 'Start word not in dictionnary.'
        assert end in self.words, 'End word not in dictionnary.'

        paths = {None: []}
        for parent, child in self._bfs(start):
            paths[child] = paths[parent] + [child]
            if child == end:
                return paths[child]
        return None

    def get_neighbours(self, word):
        '''Gets every word one letter away from the a given word.

        We do not keep these words in memory because bfs accesses 
        a given vertex only once.
        '''
        neighbours = []

        p_word = ['^' + word[0:i] + '\w' + word[i+1:] + '$' 
            for i, w in enumerate(word)]
        p_word = '|'.join(p_word)

        for w in self.words:
            if w != word and re.match(p_word, w, re.I|re.U):
                neighbours += [w]
        return neighbours

    def read_dict(self, size):
        '''Loads every word of a specific size from the dictionnary into memory.
        '''
        for l in open(self.dict_path):
            l = l.decode('latin-1').strip().lower()
            if len(l) == size:
                self.words.add(l)

if __name__ == '__main__':
    import sys
    if len(sys.argv) not in [3, 4]:
        print 'Usage: python one_letter_game.py start_word end_word'
    else:
        g = OneLetterGame(dict_path = '/usr/share/dict/words')
        try:
            g.run(*sys.argv[1:])
        except AssertionError, e:
            print e

---

感谢大家的精彩回答。我觉得真正让我困惑的是，我每次都要遍历字典中的所有单词来考虑可能的单词邻居。其实我可以使用反向索引，正如Duncan和Matt Anderson所指出的那样。A*算法也肯定会有所帮助。非常感谢，现在我知道我哪里做错了。

这里是使用反向索引的相同代码：

import collections
import functools
import re

def time_func(func):
    import time

    def wrapper(*args, **kwargs):
        start = time.time()
        res = func(*args, **kwargs)
        timed = time.time() - start

        setattr(wrapper, 'time_taken', timed)
        return res

    functools.update_wrapper(wrapper, func)
    return wrapper

class OneLetterGame:
    def __init__(self, dict_path):
        self.dict_path = dict_path
        self.words = {}

    def run(self, start_word, end_word):
        '''Runs the one letter game with the given start and end words.
        '''
        assert len(start_word) == len(end_word), \
            'Start word and end word must of the same length.'

        self.read_dict(len(start_word))

        path = self.shortest_path(start_word, end_word)
        if not path:
            print 'There is no path between %s and %s (took %.2f sec.)' % (
                start_word, end_word, self.shortest_path.time_taken)
        else:
            print 'The shortest path (found in %.2f sec.) is:\n=> %s' % (
                self.shortest_path.time_taken, ' -- '.join(path))

    def _bfs(self, start):
        '''Implementation of breadth first search as a generator.

        The portion of the graph to explore is given on demand using get_neighboors.
        Care was taken so that a vertex / node is explored only once.
        '''
        queue = collections.deque([(None, start)])
        inqueue = set([start])

        while queue:
            parent, node = queue.popleft()
            yield parent, node

            new = set(self.get_neighbours(node)) - inqueue
            inqueue = inqueue | new
            queue.extend([(node, child) for child in new])

    @time_func
    def shortest_path(self, start, end):
        '''Returns the shortest path from start to end using bfs.
        '''
        assert self.in_dictionnary(start), 'Start word not in dictionnary.'
        assert self.in_dictionnary(end), 'End word not in dictionnary.'

        paths = {None: []}
        for parent, child in self._bfs(start):
            paths[child] = paths[parent] + [child]
            if child == end:
                return paths[child]
        return None

    def in_dictionnary(self, word):
        for s in self.get_steps(word):
            if s in self.words:
                return True
        return False

    def get_neighbours(self, word):
        '''Gets every word one letter away from the a given word.
        '''
        for step in self.get_steps(word):
            for neighbour in self.words[step]:
                yield neighbour

    def get_steps(self, word):
        return (word[0:i] + '*' + word[i+1:] 
            for i, w in enumerate(word))

    def read_dict(self, size):
        '''Loads every word of a specific size from the dictionnary into an inverted index.
        '''
        for w in open(self.dict_path):
            w = w.decode('latin-1').strip().lower()
            if len(w) != size:
                continue
            for step in self.get_steps(w):
                if step not in self.words:
                    self.words[step] = [] 
                self.words[step].append(w)

if __name__ == '__main__':
    import sys
    if len(sys.argv) not in [3, 4]:
        print 'Usage: python one_letter_game.py start_word end_word'
    else:
        g = OneLetterGame(dict_path = '/usr/share/dict/words')
        try:
            g.run(*sys.argv[1:])
        except AssertionError, e:
            print e

还有一个时间比较：

% python one_letter_game_old.py happy hello 找到的最短路径（耗时 91.57秒）是：
=> happy -- harpy -- harps -- harts -- halts -- halls -- hells -- hello

% python one_letter_game.py happy hello 找到的最短路径（耗时 1.71秒）是：
=> happy -- harpy -- harps -- harts -- halts -- halls -- hells -- hello

Answer 1

也许你一开始就不想在这样的公司工作。我个人不太相信代码审查。我觉得如果你在查看求职者的作品集和过去的推荐信时做得足够好，就没必要再进行现场的代码测试了。那些有严格政策的公司，最终往往都不会成功，因为他们只雇佣那些整天想着代码的单一思维的程序员。这只是我个人的看法。

Answer 2

我同意，期待你的编程测试答案是他们选择其他人的唯一原因，这确实有点奇怪。不过，你的代码确实存在一些问题。你在每一步路径上都要在字典里进行线性搜索，也就是说要逐个查找每个可能的路径。对于一个很大的字典和很多可能的路径来说，这样做可能会花费很长时间。而且很明显，你没有进行充分的测试，因为当没有路径时，它会出错。

如果是我来写这个代码，我会在加载单词时创建一个字典，这样就可以直接挑选出下一个单词，避免线性搜索。这个代码不是完整的解决方案，但应该能让你明白我的意思：

words = {}

def get_keys(word):
    """Generate keys from a word by replacing each letter in turn by an asterisk"""
    for i in range(len(word)):
        yield word[:i]+'*'+word[i+1:]

def get_steps(word):
    """Find the set of all words that can link to the given word."""
    steps = []
    for key in get_keys(word):
        steps.extend(words[key])
    steps = set(steps) - set([word])
    return steps

# Load the dictionary
for word in ('start', 'stare', 'spare', 'spore'):
    for key in get_keys(word):
        if key not in words:
            words[key] = []
        words[key].append(word)

print(words)
print(get_steps('stare'))

Answer 3

我不会说你的解决方案是错误的，但它确实有点慢。主要有两个原因。

1. 广度优先搜索会访问所有比需要的路径短一段的路径，还有一些到全部需要长度的路径，才能给你一个答案。而最佳优先搜索（A*算法）理想情况下会跳过大部分不相关的路径。

2. 你每次寻找邻居时都在检查字典里的每一个单词，看它是否可以作为邻居。正如邓肯所建议的，你可以构建一个数据结构，基本上可以直接查找邻居，而不是一个个去找。

这里有一个解决你问题的其他方法：

import collections
import heapq
import time

def distance(start, end):
    steps = 0
    for pos in range(len(start)):
        if start[pos] != end[pos]:
            steps += 1
    return steps


class SearchHeap(object):
    def __init__(self):
        self.on_heap = set()
        self.heap = []

    def push(self, distance, word, path):
        if word in self.on_heap:
            return
        self.on_heap.add(word)
        heapq.heappush(self.heap, ((distance, len(path)), word, path))

    def __len__(self):
        return len(self.heap)

    def pop(self):
        return heapq.heappop(self.heap)


class OneLetterGame(object):
    _word_data = None

    def __init__(self, dict_path):
        self.dict_path = dict_path

    def run(self, start_word, end_word):
        start_time = time.time()
        self._word_data = collections.defaultdict(list)
        if len(start_word) != len(end_word):
            print 'words of different length; no path'
            return

        found_start, found_end = self._load_words(start_word, end_word)
        if not found_start:
            print 'start word %r not found in dictionary' % start_word
            return
        if not found_end:
            print 'end word %r not found in dictionary' % end_word
            return

        search_start_time = time.time()
        path = self._shortest_path(start_word, end_word)
        search_time = time.time() - search_start_time
        print 'search time was %.4f seconds' % search_time

        if path:
            print path
        else:
            print 'no path found from %r to %r' % (start_word, end_word)

        run_time = time.time() - start_time
        print 'total run time was %.4f seconds' % run_time

    def _load_words(self, start_word, end_word):
        found_start, found_end = False, False
        length = len(start_word)
        with open(self.dict_path) as words:
            for word in words:
                word = word.strip()
                if len(word) == length:
                    if start_word == word: found_start = True
                    if end_word == word: found_end = True
                    for bucket in self._buckets_for(word):
                        self._word_data[bucket].append(word)
        return found_start, found_end

    def _shortest_path(self, start_word, end_word):
        heap = SearchHeap()
        heap.push(distance(start_word, end_word), start_word, (start_word,))
        while len(heap):
            dist, word, path = heap.pop()
            if word == end_word:
                return path
            for neighbor in self._neighbors_of(word):
                heap.push(
                    distance(neighbor, end_word), 
                    neighbor, 
                    path + (neighbor,))
        return ()

    def _buckets_for(self, word):
        buckets = []
        for pos in range(len(word)):
            front, back = word[:pos], word[pos+1:]
            buckets.append(front+'*'+back)
        return buckets

    def _neighbors_of(self, word):
        for bucket in self._buckets_for(word):
            for word in self._word_data[bucket]:
                yield word

if __name__ == '__main__':
    import sys
    if len(sys.argv) not in [3, 4]:
        print 'Usage: python one_letter_game.py start_word end_word'
    else:
        matt = OneLetterGame(dict_path = '/usr/share/dict/words')
        matt.run(*sys.argv[1:])

还有一个时间比较：

% python /tmp/one_letter_alex.py canoe happy
The shortest path (found in 51.98 sec.) is:
=> canoe -- canon -- caxon -- taxon -- taxor -- taxer -- taper -- paper -- papey -- pappy -- happy

% python /tmp/one_letter_matt.py canoe happy
search time was 0.0020 seconds
('canoe', 'canon', 'caxon', 'taxon', 'taxor', 'taxer', 'taper', 'paper', 'papey', 'pappy', 'happy')
total run time was 0.2416 seconds