fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
前缀树算法模板秒杀五道算法题 :: labuladong的算法小抄
648题 单词替换 代码部分
// 在 Trie 树中搜索最短词根（最短前缀）
String prefix = set.shortestPrefixOf(words[i]);
if(prefix != null && !prefix.isEmpty()) {
// 如果搜索到了，改写为词根
sb.append(prefix);
} else {
// 否则，原样放回
sb.append(words[i]);
}
中间需要进行一次判空操作 ， String.isEmpty() 不能对空判断
@zhongweiLeex 贴出你的代码
-
之前是我表达错误了，实在抱歉，是需要将前面已经匹配的剪枝。然后检查剩下的。这样就不会超出时间限制，（代码格式写的比较烂，再次抱歉！）
-
之前的648题 搜索最短前缀部分，也是需要一个 判断
prefix != null的操作，因为String.isEmpty()好像只能对 字符串判断是否是空字符串，但是不能对 空值（null）判断。 -
在遇到通配符的时候 ，就不维护原来的，新建一个，因为如果前面的都匹配了，那前面的就必要拖着整个回溯了，直接查找后面的就行。
class WordDictionary {
private Node root = null;
private int size = 0;
public WordDictionary() {
}
private static class Node {
boolean end = false;
Node[] children = new Node[26];
}
private Node getNode(Node node , String key){
Node p = root;
for (int i = 0; i < key.length(); i++) {
if (p == null){
return null;
}
char c = key.charAt(i);
p = p.children[c-'a'];
}
return p;
}
public boolean get(String key){
Node p = getNode(root,key);
if (p == null || p.end == false){
return false;
}
return p.end;
}
public void addWord(String word) {
root = addWord(root,word,0);
}
private Node addWord(Node node , String key, int i){
if (node == null){
node = new Node();
}
if (i == key.length()){
node.end = true;
return node;
}
char c= key.charAt(i);
node.children[c-'a'] = addWord(node.children[c-'a'],key,i+1);
return node;
}
public boolean search(String word) {
char[] pattern = word.toCharArray();
return search(root,pattern,0);
}
private boolean search(Node node,char[] pattern,int i){
if(node == null){
return false;
}
if(i == pattern.length){
return node.end;
}
char c = pattern[i];
if (c == '.'){
for (int j = 0; j < 26; j++) {
if(node == null){
return false;
}
if (node.children[j] == null){
continue;
}
Node newNode = node.children[j];
if (search(newNode,pattern,i+1)){
return true;
}
}
}else{
int k = pattern[i] - 'a';
if(node == null){
return false;
}
if (node.children[k] == null){
return false;
}
node = node.children[k];
if (search(node,pattern,i+1)){
return true;
}
}
return false;
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
感觉648直接用string 的join比StringBuilder省事一点呢
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
// put the dict in a trie set and use the shortestPrefixOf method
TrieSet dict = new TrieSet();
for (String root : dictionary) {
dict.add(root);
}
String[] words = sentence.split(" ");
for (int i = 0; i < words.length; ++i) {
String prefix = dict.shortestPrefixOf(words[i]);
// if prefix can be found, replace
if (!prefix.isEmpty()) {
words[i] = prefix;
}
}
return String.join(" ", words);
}
}
211 只要把children 数组大小优化成26就不会超时啦
class WordDictionary {
private final TrieMap<Object> map;
public WordDictionary() {
map = new TrieMap<>();
}
public void addWord(String word) {
// use key to store word, Object as placehoder
map.put(word, new Object());
}
public boolean search(String word) {
// has '.'
return map.hasKeyWithPattern(word);
}
}
class TrieMap<V> {
private static final int R = 26;
private int size = 0;
private class TrieNode<V> {
V val = null;
TrieNode<V>[] children = new TrieNode[R];
}
private TrieNode<V> root = null;
// methods
public void put(String word, V val) {
if (!containsKey(word)) {
size++;
}
root = put(root, word, val, 0);
}
private TrieNode<V> put(TrieNode<V> node, String key, V val, int i) {
if (node == null) {
node = new TrieNode<>();
}
if (i == key.length()) {
node.val = val;
return node;
}
char c = key.charAt(i);
node.children[c - 'a'] = put(node.children[c - 'a'], key, val, i + 1);
return node;
}
public boolean hasKeyWithPattern(String pattern) {
return hasKeyWithPattern(root, pattern, 0);
}
// recursion helper
private boolean hasKeyWithPattern(TrieNode<V> node, String pattern, int i) {
if (node == null) {
// cannot continue
return false;
}
if (i == pattern.length()) {
// reaches the end
return node.val != null;
}
char c = pattern.charAt(i);
if (c != '.') {
// if not .
return hasKeyWithPattern(node.children[c - 'a'], pattern, i + 1);
}
for (int j = 0; j < R; ++j) {
// see every possible char, return if any has val
if (hasKeyWithPattern(node.children[j], pattern, i + 1)) {
// as long as one child has this patten
return true;
}
// NOTE: NOT return hasKeyWithPattern(node.children[j], pattern, i + 1);
}
// nothing matched
return false;
}
private TrieNode<V> getNode(TrieNode<V> node, String key) {
// search downwards from node
TrieNode<V> p = node;
for (int i = 0; i < key.length(); ++i) {
if (p == null) {
return null;
}
char c = key.charAt(i);
p = p.children[c - 'a'];
}
return p;
}
private V get(String key) {
TrieNode<V> x = getNode(root, key);
if(x == null || x.val == null) {
return null;
}
return x.val;
}
private boolean containsKey(String key) {
return get(key) != null;
}
}
迷惑，，我直接套到design-add-and-search-words-data-structure里面，遇到pattern直接返回竟然比返回所有结果还慢很多，有的尝试直接TLE