z***b 发帖数: 127 | 1 trie的搜索, 和leetcode 有些不同。
class Node {
Node getChildForLetter(letter)
Node[] getAllChildren();
bool isTerminal();
}
搜索返回所有符合wildcard的词
比如
add("car")
add("caw")
add("cauw")
search("c*w") should return "caw" and "cauw".
* could be at any place in the input string. |
Y****n 发帖数: 7 | 2 使用回溯的办法,对 * 匹配 0 - n个字符,使用一个path记录走过的每个字符。除了
回溯暂时没想到什么好办法。 |
b*******w 发帖数: 56 | 3 def search(self, pattern):
if not pattern:
return [''] if self.isTerminal() else []
matches = []
if pattern == '*':
if self.isTerminal():
matches.append('')
for letter in string.lowercase:
child = self.getChildForLetter(letter)
if child:
matches.extend([(letter + m) for m in child.search(pattern)])
else:
met_wildcard = True if pattern[0] == "*" else False
for letter in string.lowercase:
child = lf.getChildForLetter(letter)
if child:
if met_wildcard:
if letter == pattern[1]:
matches.extend([(letter + m) for m in child.search(
pattern[2:])])
else:
matches.extend([letter + m for m in child.search(
pattern)])
else:
if letter == pattern[0]:
matches.extend([(letter + m) for m in child.search(
pattern[1:])])
else:
matches = []
return matches |
l******8 发帖数: 1691 | 4 dfs应该就可以。从c开始往下,recursive,保持一个当前字段,一点点延长,一直找
到终点,最后是w就把当前字段加入到resutls。然后从当前字段每次删除最后一个字符
,返回,即续找。最后返回results。
【在 z***b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : trie的搜索, 和leetcode 有些不同。 : class Node { : Node getChildForLetter(letter) : Node[] getAllChildren(); : bool isTerminal(); : } : 搜索返回所有符合wildcard的词 : 比如 : add("car") : add("caw")
|