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 的大作中提到】
: trie的搜索, 和leetcode 有些不同。
: class Node {
: Node getChildForLetter(letter)
: Node[] getAllChildren();
: bool isTerminal();
: }
: 搜索返回所有符合wildcard的词
: 比如
: add("car")
: add("caw")
|
