Trie, Hash & BF solutions w/ C++ & Python


  • 0
    Z

    c++ trie solution:

    class Solution {
    public:
        string replaceWords(vector<string>& dict, string sentence) {
            struct sTrie {
                sTrie * next[26] = {};
                string word;
                ~sTrie() {
                    for ( int i = 0; i < 26; ++i )
                        if ( next[i] )
                            delete next[i];
                }
            };
            sTrie * t = new sTrie();
            for ( string & w : dict ) {
                sTrie * cur = t;
                for ( char c : w ) {
                    if ( nullptr == cur->next[c - 'a'] )
                        cur->next[c - 'a'] = new sTrie();
                    cur = cur->next[c - 'a'];
                }
                cur->word = w;
            }
            string result, word;
            istringstream iss(sentence);
            while ( iss >> word ) {
                sTrie * cur = t;
                for ( char c : word ) {
                    if ( cur->word.size() > 0 ) {
                        word = cur->word;
                        break;
                    }
                    if ( nullptr == cur->next[c - 'a'] )
                        break;
                    cur = cur->next[c - 'a'];
                }
                result += word + ' ';
            }
            delete t;
            result.pop_back();
            return result;
        }
    };
    
    // 124 / 124 test cases passed.
    // Status: Accepted
    // Runtime: 65 ms
    

    c++ hash solution:

    class Solution {
    public:
        string replaceWords(vector<string>& dict, string sentence) {
            // inspired by @ SlavaSSU
            unordered_map<double, string> m;
            for ( auto & w : dict ) {
                double cur = 1, base = 26, hash = 0;
                for ( char c : w ) {
                    hash = hash + (c - 'a' + 1) * cur;
                    cur *= base;
                }
                m[hash] = w;
            }
            string result, word;
            istringstream iss(sentence);
            while ( iss >> word ) {
                double cur = 1, base = 26, hash = 0;
                for ( int i = 0; i < word.size(); ++i ) {
                    hash = hash + (word[i] - 'a' + 1) * cur;
                    cur *= base;
                    if ( m.count(hash) ) {
                        word = word.substr(0, i + 1);
                        break;
                    }
                }
                result += word + " ";
            }
            result.pop_back();
            return result;
        }
    };
    
    // 124 / 124 test cases passed.
    // Status: Accepted
    // Runtime: 72 ms
    

    c++ brute force solution:

    class Solution {
    public:
        string replaceWords(vector<string>& dict, string sentence) {
            unordered_set<string> d(dict.begin(), dict.end());
            string result, word, wordsub;
            istringstream iss(sentence);
            while ( iss >> word ) {
                for ( int i = 1; i <= word.size(); ++i ) {
                    wordsub = word.substr(0, i);
                    if ( d.find(wordsub) != d.end() ) {
                        word = wordsub;
                        break;
                    }
                }
                result += word + ' ';
            }
            result.pop_back();
            return result;
        }
    };
    
    // 124 / 124 test cases passed.
    // Status: Accepted
    // Runtime: 189 ms
    

    python trie solution:

    class Solution(object):
        def replaceWords(self, dict, sentence):
            """
            :type dict: List[str]
            :type sentence: str
            :rtype: str
            """
            t = {}
            for word in dict:
                cur = t
                for c in word:
                    cur = cur.setdefault(c, {})
                cur['$'] = word
            senwords = sentence.split()
            for i in xrange(len(senwords)):
                word = senwords[i]
                cur = t
                for c in word:
                    cur = cur.get(c)
                    if not cur:
                        break
                    if '$' in cur:
                        senwords[i] = cur['$']
                        break
            return ' '.join(senwords)
    
    # 124 / 124 test cases passed.
    # Status: Accepted
    # Runtime: 128 ms
    

    python hash solution:

    class Solution(object):
        def replaceWords(self, dict, sentence):
            """
            :type dict: List[str]
            :type sentence: str
            :rtype: str
            """
            hashmap = {}
            for word in dict:
                h, cur, base = 0, 1, 26
                for c in word:
                    h += (ord(c) - 96) * cur
                    cur *= base
                hashmap[h] = word
            result = sentence.split()
            for i in xrange(len(result)):
                h, cur, base = 0, 1, 26
                for c in result[i]:
                    h += (ord(c) - 96) * cur
                    if h in hashmap:
                        result[i] = hashmap[h]
                        break
                    cur *= base
            return ' '.join(result)
    
    # 124 / 124 test cases passed.
    # Status: Accepted
    # Runtime: 555 ms
    

    python brute force solution:

    class Solution(object):
        def replaceWords(self, dict, sentence):
            """
            :type dict: List[str]
            :type sentence: str
            :rtype: str
            """
            d, result = set(dict), []
            for word in sentence.split():
                for i in xrange(1, len(word) + 1):
                    if word[:i] in d:
                        result.append(word[:i])
                        break
                else:
                    result.append(word)
            return ' '.join(result)
    
    # 124 / 124 test cases passed.
    # Status: Accepted
    # Runtime: 452 ms
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.