648. Replace Words

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class TrieNode{
public:
    TrieNode *children[26];
    bool isWord;
    TrieNode (){
        for(TrieNode* &child:this->children) child = nullptr;
        this->isWord = false;
    }
    
};
class Trie{
private:
    TrieNode *root;
public:
    Trie (){
        root = new TrieNode();
    }
    void insert(string word){
        TrieNode *p = root;
        for(char c:word){
            if(!p->children[c-'a']) p->children[c-'a'] = new TrieNode();
            p=p->children[c-'a'];
        }
        p->isWord= true;
    }
    bool search(string word){
        TrieNode *p = root;
        for(char c:word){
            if(!p->children[c-'a']) return false;
            p=p->children[c-'a'];
        }
        return p->isWord;
    }
    bool startsWith(string word){
        TrieNode *p = root;
        for(char c:word){
            if(!p->children[c-'a']) return false;
            p=p->children[c-'a'];
        }
        return true;
    }
    string shortestPrefixOf(string word){
        string ret;
        TrieNode *p = root;
        for(int i=0;i<word.size() ; ++i){
            char c = word[i];
            if(p->children[c-'a']) {
                ret+=string(1,c);
                p=p->children[c-'a'];
            }
            else return "";
            
            if(p->isWord) return ret;
        }
        return "";
    }
};


class Solution {
public:
    vector<string> split(string sentence){
        int j=0;
        int n= sentence.size();
        vector<string> words ;
        while(j<n && sentence[j]==' ') j++;
        int i;
        for(i=j;i<n;++i){
            if(sentence[i] ==' '){
                words.push_back(sentence.substr(j, i-j));
                j=i+1;
            }
        }
        words.push_back(sentence.substr(j, i-j));
        return words;
        
    }
    string replaceWords(vector<string>& dictionary, string sentence) {
        // 將dictionary 放入Trie  
        Trie *t = new Trie();
        for(string s:dictionary){
            t->insert(s);
        }
        vector<string> words = split(sentence);
        string ret ;
        
        int len = words.size();
        for(int i=0;i<len; ++i){
            string prefix = t->shortestPrefixOf(words[i]);
            if(!prefix.empty()) ret+=prefix;
            else ret+=words[i];
            if(i<len-1) ret+=' ';
        }
        return ret;
        
    }
};