优于网上博客:动态规划+字典树,LeetCode 139. Word Break


我个人觉得,这道题这么做给个Hard是不过分的,但是效率是比网上博客上大多数答案要好很多,也更有逼格。

思路是从许老师那来的,不得不说许老师6666,网上都是看不到这么好的思路的。

动态规划部分:ans[i] 表示字符串[0...i-1]位置的字符都可以被字典中的词表示。
字典树部分:把字典中所有的词都存进去,然后碰到ans[i]可以被字典中的词表示,那么久从s[i]开始找到所有的ans[i + k]标记为true。
class TrieNode{
public:
    bool isWord;
    TrieNode *child[26];
    
    TrieNode(){
        isWord = false;
        memset(child, NULL, sizeof(child));
    }
};

class Solution {
public:
    TrieNode *root = NULL;
    bool wordBreak(string s, vector<string>& wordDict) {
        if (s.size() == 0 || wordDict.size() == 0){
            return false;
        }
        
        root = new TrieNode();
        for (vector<string>::iterator it = wordDict.begin(); it != wordDict.end(); ++it){
            Insert(root, *it);
        }
        
        bool ans[100000];
        memset(ans, false, sizeof(ans));
        
        ans[0] = true;
        
        for (int i = 0; i < s.size(); ++i){
            if(ans[i]){
                TrieNode *t = root;
                for (int j = i; j < s.size(); ++j){
                    int id = s[j] - 'a';
                    if (t->child[id] == NULL){
                        break;
                    }                  
                    t = t->child[id];
                    if(t->isWord){
                        ans[j + 1] = true;
                    }                       
                }
            }
        }
        
        return ans[s.size()];
    }
    
    void Insert(TrieNode *root, string &str){
        TrieNode *r = root;
        for (int i = 0; i < str.size(); ++i){
            int id = str[i] - 'a';
            if (r->child[id] == NULL){
                r->child[id] = new TrieNode();
            }
            r = r->child[id];
        }
        r->isWord = true;
    }
};
已邀请:

July - 抠细节抠体验,不妥协不将就。

赞同来自:


运行时间 多长呀

要回复问题请先登录注册

返回顶部