算法编程中的Word 四兄弟 Word Break , Word Ladder, Word Search, Word Pattern

Word 四兄弟 Word Break , Word Ladder, Word Search, Word Pattern， 太容易出现了，针对性分析下。

829 · 字模式 II

算法

困难

通过率47%

描述

给定一个pattern和一个字符串str，查找str是否遵循相同的模式。
这里遵循的意思是一个完整的匹配，在一个字母的模式和一个非空的单词str之间有一个双向连接的模式对应。(如果a对应s，那么b不对应s。例如，给定的模式= "ab"， str = "ss"，返回false）。

您可以假设模式和str只包含小写字母

样例

样例1

输入:
pattern = "abab"
str = "redblueredblue"
输出: true
说明: "a"->"red","b"->"blue"

样例2

输入:
pattern = "aaaa"
str = "asdasdasdasd"
输出: true
说明: "a"->"asd"

样例3

输入:
pattern = "aabb"
str = "xyzabcxzyabc"
输出: false

class Solution:
    """
    @param pattern: a string,denote pattern string
    @param str: a string, denote matching string
    @return: a boolean
    """
    def wordPatternMatch(self, pattern, string):
        return self.is_match(pattern, string, {}, {})

    def is_match(self, pattern, string, mapping, mapping2):
        if not pattern:
            return not string
            
        char = pattern[0]
        if char in mapping:
            word = mapping[char]
            if not string.startswith(word):
                return False
            return self.is_match(pattern[1:], string[len(word):], mapping, mapping2)
            
        for i in range(len(string)):
            word = string[:i + 1]
            if word in mapping2:
                continue
            
            mapping2[word] = char
            mapping[char] = word
            
            if self.is_match(pattern[1:], string[i + 1:], mapping, mapping2):
                return True
            
            del mapping[char]
            del mapping2[word]
                        
        return False

要点：

if word in mapping2:
      continue
理解下：

这里我们为什么需要一个额外的 mapping2 呢？ 
		  
			一个好的测试用例是:
			pattern:    "bdpbibletwuwbvh"
			str:        "aaaaaaaaaaaaaaa"
			
		 这里第一次执行时， mapping中匹配了 b -> a 
		 递归进去以后第二次执行时，d 没有在 mapping 中，所以跳过了map的匹配检测，
		 所以进入循环体， 这时第二个word 又是 a, 按道理 a 应该被 b 匹配并且之前应该在mapping.containsKey的检查中跳出， 但现在并没有跳出，而是试图绑匹配给另一个pattern的字母 d, 
		 很明显 b != d 重复绑定不是正确结果， 所以需要continue掉这次尝试。
		 
		 当然， 我们可以直接用map.containsValue(d), 因为之前map检查中己经跳出了如果己经绑定过，现在又出现了，就意味着重复绑定， 或者说不是匹配的。 
                之所以单独开了这个mapping2 因为map.containsValue需要额外的O(n)时间， 实际上就是以空间换时间或时间换空间的选择。

单词接龙 II · Word Ladder II

给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列。

变换规则如下：

1. 每次只能改变一个字母。
2. 变换过程中的中间单词必须在字典中出现。
3. 所有单词具有相同的长度。
4. 所有单词都只包含小写字母。
5. 题目确保存在合法的路径。

样例

样例 1：

输入：

start = "a"
end = "c"
dict =["a","b","c"]

输出：

[["a","c"]]

解释：

"a"->"c"

样例 2：

输入：

start ="hit"
end = "cog"
dict =["hot","dot","dog","lot","log"]

输出：

[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

解释：

1."hit"->"hot"->"dot"->"dog"->"cog"
2."hit"->"hot"->"lot"->"log"->"cog"

用dijstra算法会出现mem超出限制！！！
先用bfs找到target距离，再用dfs寻找路径，会超时。。。你妹哦！

from typing import (
    List,
    Set,
)
import heapq


class Solution:
    """
    @param start: a string
    @param end: a string
    @param dict: a set of string
    @return: a list of lists of string
             we will sort your return value in output
    """
    def find_ladders(self, start: str, end: str, dict: Set[str]) -> List[List[str]]:
        # write your code here
        self.next_word_dict = {}
        distance = self.bfs(start, end, dict)
        self.ans = []
        print("distance", distance)
        
        self.dfs(start, end, dict, distance, layer=0, path=[start])
        return self.ans

    def bfs(self, start, end, mapping):        
        mapping.add(end)

        q = [start]
        seen = {start}
        distance = 0

        while q:
            # print("q=>", q)            
            q2 = []
            distance += 1
            for virtex in q:
                for word in self.get_neibors(virtex, mapping):                
                    if word not in seen:
                        q2.append(word)                    
                        seen.add(word)

                    if word == end:
                        return distance
            #print("q", q)
            #print("q2", q2)
            q = q2
                    
        return distance
    
    def get_neibors(self, word, words_set):
        if word in self.next_word_dict:
            return self.next_word_dict[word]

        words = []
        for i in range(len(word)):
            left, right = word[:i], word[i + 1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if word[i] == char:
                    continue
                 
                word2 = left + char + right              
                if word2 in words_set:                   
                    words.append(word2)
        
        self.next_word_dict[word] = words
        return words

    def dfs(self, start, end, mapping, distance, layer, path):
        if layer == distance:
            if end == start:
                self.ans.append(list(path))
            return
        
        for word in self.get_neibors(start, mapping):   
            # if word not in path:  
            if len(path) < 2 or word != path[-2]:              
                path.append(word)
                # print("paht:", path)
                self.dfs(word, end, mapping, distance, layer+1, path)
                path.pop()

优化下，使用distance记录bfs中的节点到start的距离，然后在dfs遍历中，看是否满足距离，这样去卡dfs的节点：（使用BFS的原因为了预处理出最短路径。如果只使用DFS会超时因为会遍历所有的可能。）

from typing import (
    List,
    Set,
)
import heapq


class Solution:
    """
    @param start: a string
    @param end: a string
    @param dict: a set of string
    @return: a list of lists of string
             we will sort your return value in output
    """
    def find_ladders(self, start: str, end: str, dict: Set[str]) -> List[List[str]]:
        # write your code here
        self.next_word_dict = {}
        distance = self.bfs(start, end, dict)
        self.ans = []
        # print("distance", distance)
        
        self.dfs(start, end, dict, distance, layer=0, path=[start])
        return self.ans

    def bfs(self, start, end, mapping):        
        mapping.add(end)

        q = [start]
        seen = {start}
        distance = {}
        layer = 0

        while q:       
            q2 = []
            layer += 1
            for virtex in q:
                for word in self.get_neibors(virtex, mapping):                
                    if word not in distance:
                        q2.append(word)                    
                        distance[word] = layer

                    if word == end:
                        return distance

            q = q2
                    
        return distance
    
    def get_neibors(self, word, words_set):
        if word in self.next_word_dict:
            return self.next_word_dict[word]

        words = []
        for i in range(len(word)):
            left, right = word[:i], word[i + 1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if word[i] == char:
                    continue
                 
                word2 = left + char + right              
                if word2 in words_set:                   
                    words.append(word2)
        
        self.next_word_dict[word] = words
        return words

    def dfs(self, start, end, mapping, distance, layer, path):
        if end == start:
            self.ans.append(list(path))
            return
        
        for word in self.get_neibors(start, mapping):   
            if word in distance and distance[word] == layer+1:
                path.append(word)
                self.dfs(word, end, mapping, distance, layer+1, path)
                path.pop()

单词搜索 II · Word Search II

深度优先搜索/回溯法哈希表微软爱彼迎谷歌LintCode Copyright字典树

描述中文

给出一个由小写字母组成的矩阵和一个字典。找出所有同时在字典和矩阵中出现的单词。一个单词可以从矩阵中的任意位置开始，可以向左/右/上/下四个相邻方向移动。一个字母在一个单词中只能被使用一次。且字典中不存在重复单词

样例

样例 1:

输入：["doaf","agai","dcan"]，["dog","dad","dgdg","can","again"]
输出：["again","can","dad","dog"]
解释：
  d o a f
  a g a i
  d c a n
矩阵中查找，返回 ["again","can","dad","dog"]。

样例 2:

输入：["a"],["b"]
输出：[]
解释：
 a
矩阵中查找，返回 []。

挑战

使用单词查找树来实现你的算法

直接暴力做要悲剧，todo，trie写下。。。