难度: Medium
Submission
运行时间: 32 ms
内存: 0.0 MB
from copy import deepcopy
class Solution:
def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
similarWords = {}
self.output = []
for pair in synonyms:
first = pair[0]
second = pair[1]
if first in similarWords and second in similarWords:
continue
if first not in similarWords and second not in similarWords:
similarWords[first] = set([second])
similarWords[second] = set([first])
continue
existed, notExisted = first, second
if existed not in similarWords:
existed, notExisted = second, first
similarWords[notExisted] = set()
for word in similarWords[existed]:
similarWords[word].add(notExisted)
similarWords[notExisted].add(word)
similarWords[notExisted].add(existed)
similarWords[existed].add(notExisted)
self.backtracker(0, text.split(' '), similarWords)
return sorted(self.output)
def backtracker(self, curIndex, wordsList, similarWords):
if curIndex == len(wordsList):
self.output.append(' '.join(wordsList))
return
self.backtracker(curIndex + 1, wordsList, similarWords)
if wordsList[curIndex] in similarWords:
for synonym in similarWords[wordsList[curIndex]]:
wordsList[curIndex] = synonym
self.backtracker(curIndex + 1, wordsList, similarWords)
Explain
题解采用了回溯算法来生成所有可能的句子。首先，通过建立一个映射表 `similarWords` 来记录每个单词可以互为近义词的所有单词。然后使用 `backtracker` 函数递归地探索每个单词的所有可能的近义词替换，生成所有可能的句子组合。最后，将结果排序后返回。
时间复杂度: O((m+1)^n)
空间复杂度: O(n + k)
from copy import deepcopy
class Solution:
def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
similarWords = {}
self.output = []
for pair in synonyms:
first, second = pair
if first in similarWords and second in similarWords:
continue
if first not in similarWords and second not in similarWords:
similarWords[first] = set([second])
similarWords[second] = set([first])
continue
existed, notExisted = (first, second) if first in similarWords else (second, first)
similarWords[notExisted] = set()
for word in similarWords[existed]:
similarWords[word].add(notExisted)
similarWords[notExisted].add(word)
similarWords[notExisted].add(existed)
similarWords[existed].add(notExisted)
self.backtracker(0, text.split(' '), similarWords)
return sorted(self.output)
def backtracker(self, curIndex, wordsList, similarWords):
if curIndex == len(wordsList):
self.output.append(' '.join(wordsList))
return
self.backtracker(curIndex + 1, wordsList, similarWords)
if wordsList[curIndex] in similarWords:
originalWord = wordsList[curIndex]
for synonym in similarWords[wordsList[curIndex]]:
wordsList[curIndex] = synonym
self.backtracker(curIndex + 1, wordsList, similarWords)
wordsList[curIndex] = originalWord # Restore the original word after recursion
Explore
在构建`similarWords`映射表时，如果两个单词均未出现过，意味着这两个单词之间的相似关系是独立于其他单词的关系。此时，没有足够的信息将这两个单词与其他已有单词关联起来。因此，只建立这两个单词之间的双向映射是为了避免错误地假设未验证的近义词关系，从而确保映射表的准确性和一致性。
当处理已有单词与未出现过的单词建立映射时，将新单词添加到已有单词的近义词集合中，同时也需要将新单词与已有单词的所有近义词建立连接，这是为了保持近义词网络的完整性。如果仅将新单词加入到已有单词的近义词集合，但不更新其他相关的近义词关系，将导致近义词网络不连贯，从而可能影响后续生成句子的正确性。
在`backtracker`函数中，首先尝试不替换当前单词是为了保留原始句子结构的一个选择。这种策略确保了生成的句子列表中包含了从完全不替换任何单词到替换所有可能单词的所有组合。这样做不仅保证了解集的完整性，还有助于确保递归过程中能够探索到所有有效的句子构造方式。
在使用`backtracker`函数进行递归时，需要在每次递归结束后恢复原来的单词以保持原始单词列表的状态不变。这是因为在递归过程中修改了单词列表的内容，如果不恢复原来的单词，那么这些修改会影响到后续递归调用的上下文，导致生成错误的句子。通过恢复原来的单词，可以确保每次递归调用都是从相同的状态开始，从而正确地探索所有可能的句子组合。