leetcode-720 Longest Word in Dictionary

Posted on | In , | |
Words count in article: 548 | Reading time ≈ 3

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input:

words = [“w”,”wo”,”wor”,”worl”, “world”]

Output: “world”

Explanation:

The word “world” can be built one character at a time by “w”, “wo”, “wor”, and “worl”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end());
        string ret;
        unordered_set<string> tri;
        
        for(auto str: words){
            if(str.size() == 1 || tri.count(str.substr(0, str.size()-1))){
                ret = str.size() > ret.size() ? str : ret;
                tri.insert(str);
            }
        }
        return ret;
    }
};
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
class Solution {
public:
    struct Node{
        bool isWord;
        Node* next[26];
    };
    string ret = "";
    
    string longestWord(vector<string>& words) {
        Node* root = new Node();
        root->isWord = true;
        
        for(int i=0 ;i<words.size(); i++){
            Node* tmp = root;
            for(int j=0; j<words[i].size(); j++){
                if(tmp->next[words[i][j]-'a']==NULL)
                    tmp->next[words[i][j]-'a'] = new Node();
                tmp = tmp->next[words[i][j]-'a'];
            }
            tmp->isWord = true;
        }
        
        DFS(root, "");
        return ret;
    }
    
    void DFS(Node* root, string path){
        if(root == NULL || root->isWord == false){
            path.pop_back();
            if(path.size() > ret.size()) ret = path;
            else if(path.size() == ret.size()  &&  ret > path) ret = path;
            return;
        }
        for(int i=0; i<26; i++){
            path.append(1, 'a'+i);
            DFS(root->next[i], path);
            path.pop_back();
        }
    }
};

648. Replace Words

1
2
3
Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
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
class Solution {
public:
    struct Node{
        bool isWord;
        Node* next[26];
    };
   
    string replaceWords(vector<string>& dict, string sentence) {
        Node* root = new Node();
        root->isWord = true;
        string ret = "";
        
        for(int i=0; i<dict.size(); i++)
        {
            Node* tmp = root;
            for(int j=0; j<dict[i].size(); j++){
                if(tmp->next[dict[i][j]-'a'] == NULL)
                    tmp->next[dict[i][j]-'a'] = new Node();
                tmp = tmp->next[dict[i][j]-'a'];
            }
            tmp->isWord = true;
        }
        
        string tmpstr = "";
        
        for(int i=0; i<sentence.size(); i++){
            if(sentence[i] == ' ' || i == sentence.size()-1){
                if(i == sentence.size()-1)
                    tmpstr += sentence[i];
                Node* t = root;
                int flag = 0;
                int curj = 0;
                for(int j=0; j<tmpstr.size(); j++){
                    if(t->isWord == true && t != root)
                    {
                        flag = 1;
                        curj = j;
                        break;
                    }
                    if(t->next[tmpstr[j]-'a'] != NULL)
                        t = t->next[tmpstr[j]-'a'];
                    else
                        break;
                }
                if(flag == 1){
                    for(int z=0; z<curj; z++)
                        ret += tmpstr[z];
                    tmpstr = "";
                }
                else{
                    ret += tmpstr;
                    tmpstr = "";
                }
                
                if(i != sentence.size()-1)
                    ret += " ";
                
            }
            else{
                tmpstr += sentence[i];
            }
        }
        
        return ret;
    }
};
Donate? comment?