登录
  • #码农类general
  • #工作信息
  • #找工就业
  • #facebook
  • #求职(非面经)

这一‌‌‌‌‍‍‌‍‌‌‍‍‍‌‌‍‍‌‍‍‌‌‌‍‌‌‌‍‌‍‍‌题这么写对么?

zlove
721
4
面的一家大厂。后来hr说,这一轮coding,就是dictionary,先加一些词。然后,判断,有没有。一个dot表示一个字母,任意的。fo. 和foo是match的。我做的就是用trie写的。改写了search 成strongSearch。请各位看看。



class Trie {

public TrieNode root;

public Trie() {

root = new TrieNode();

}



public void insert(String word) {

TrieNode cur = root;

for (char c : word.toCharArray()) {

if (cur.branches[c-'a'] == null) {

cur.branches[c-'a'] = new TrieNode();

}

cur = cur.branches[c-'a'];

}

cur.endWord = true;

}

public boolean strongSearch(TrieNode node, String word, int p) {

if (node == null)

return false;

char c = word.charAt(p);

if (c !='.') {

if (node.branches[c-'a'] == null)

return false;

else {

if(p == word.length()-1){

return node.branches[c-'a'].endWord;

}

return smartSearch(node.branches[c-'a'], word, p+1);

}

} else {

for (int i = 0; i < 26; i++) {

if(node.branches != null) {

if(p == word.length()-1)

return node.branches.endWord;

if (smartSearch(node.branches, word, p+1))

return true;

}

}

}

return false;

}



public boolean search(String word) {

TrieNode cur = root;

for (char c : word.toCharArray()) {

if (cur.branches[c-'a'] == null) {

return false;

}

cur = cur.branches[c-'a'];

}

return cur.endWord;

}



public boolean startsWith(String prefix) {

TrieNode cur = root;

for (char c : prefix.toCharArray()) {

if (cur.branches[c-'a'] == null) {

return false;

}

cur = cur.branches[c-'a'];

}

return true;

}

}

class TrieNode {

public boolean endWord;

public TrieNode[] branches;[br]
public TrieNode() {

endWord = false;

branches = new TrieNode[26];

}
4条回复
热度排序

发表回复