Formatted question description: https://leetcode.ca/all/648.html

648. Replace Words (Medium)

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

 

Note:

  1. The input will only have lower-case letters.
  2. 1 <= dict words number <= 1000
  3. 1 <= sentence words number <= 1000
  4. 1 <= root length <= 100
  5. 1 <= sentence words length <= 1000

 

Companies:
Uber, Adobe

Related Topics:
Hash Table, Trie

Solution 1. Trie

// OJ: https://leetcode.com/problems/replace-words/
// Time: O(D + S) where D is size of all contents in dictionary, S is size of all contents in sentence
// Space: O(D)
class TrieNode {
public:
    TrieNode *next[26] = {};
    bool isWord = false;
};
class Trie {
private:
    TrieNode root;
public:
    void insert(string &s) {
        auto node = &root;
        for (char c : s) {
            if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
            node = node->next[c - 'a'];
        }
        node->isWord = true;
    }
    string getWord(string &s) {
        auto node = &root;
        for (int i = 0; i < s.size(); ++i) {
            if (!node->next[s[i] - 'a']) return s;
            node = node->next[s[i] - 'a'];
            if (node->isWord) return s.substr(0, i + 1);
        }
        return s;
    }
};
class Solution {
public:
    string replaceWords(vector<string>& dict, string sentence) {
        istringstream ss(sentence);
        string word, ans;
        Trie trie;
        for (auto s : dict) trie.insert(s);
        while (ss >> word) ans += trie.getWord(word)+ " ";
        ans.pop_back();
        return ans;
    }
};

Java

  • class Solution {
        TrieNode root = new TrieNode();
    
        public String replaceWords(List<String> dict, String sentence) {
            createTrie(dict);
            String[] array = sentence.split(" ");
            int length = array.length;
            for (int i = 0; i < length; i++) {
                int prefixLength = searchPrefix(array[i]);
                if (prefixLength > 0)
                    array[i] = array[i].substring(0, prefixLength);
            }
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < length; i++)
                sb.append(array[i] + " ");
            sb.deleteCharAt(sb.length() - 1);
            return sb.toString();
        }
    
        public void createTrie(List<String> dict) {
            for (String prefix : dict) {
                TrieNode node = root;
                int length = prefix.length();
                for (int i = 0; i < length; i++) {
                    char letter = prefix.charAt(i);
                    int index = letter - 'a';
                    if (node.next[index] == null)
                        node.next[index] = new TrieNode();
                    node = node.next[index];
                }
                node.isEnd = true;
            }
        }
    
        public int searchPrefix(String word) {
            TrieNode node = root;
            int length = word.length();
            for (int i = 0; i < length; i++) {
                char letter = word.charAt(i);
                int index = letter - 'a';
                if (node.isEnd)
                    return i;
                else if (node.next[index] == null)
                    return 0;
                else
                    node = node.next[index];
            }
            return node.isEnd ? length : 0;
        }
    }
    
    class TrieNode {
        boolean isEnd;
        TrieNode[] next;
    
        public TrieNode() {
            isEnd = false;
            next = new TrieNode[26];
        }
    }
    
  • // OJ: https://leetcode.com/problems/replace-words/
    // Time: O(D + S) where D is size of all contents in dictionary, S is size of all contents in sentence
    // Space: O(D)
    class TrieNode {
    public:
        TrieNode *next[26] = {};
        bool isWord = false;
    };
    class Trie {
    private:
        TrieNode root;
    public:
        void insert(string &s) {
            auto node = &root;
            for (char c : s) {
                if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
                node = node->next[c - 'a'];
            }
            node->isWord = true;
        }
        string getWord(string &s) {
            auto node = &root;
            for (int i = 0; i < s.size(); ++i) {
                if (!node->next[s[i] - 'a']) return s;
                node = node->next[s[i] - 'a'];
                if (node->isWord) return s.substr(0, i + 1);
            }
            return s;
        }
    };
    class Solution {
    public:
        string replaceWords(vector<string>& dict, string sentence) {
            istringstream ss(sentence);
            string word, ans;
            Trie trie;
            for (auto s : dict) trie.insert(s);
            while (ss >> word) ans += trie.getWord(word)+ " ";
            ans.pop_back();
            return ans;
        }
    };
    
  • class TrieNode(object):
      def __init__(self):
        self.children = {}
        self.isWord = False
        self.word = ""
    
    
    class Solution(object):
      def replaceWords(self, dict, sentence):
        """
        :type dict: List[str]
        :type sentence: str
        :rtype: str
        """
        root = TrieNode()
        for word in dict:
          p = root
          for c in word:
            if c not in p.children:
              p.children[c] = TrieNode()
            p = p.children[c]
          p.isWord = True
          p.word = word
    
        words = sentence.split()
        for i in range(len(words)):
          p = root
          for c in words[i]:
            if c in p.children:
              p = p.children[c]
              if p.isWord:
                words[i] = p.word
                break
            else:
              break
        return " ".join(words)
    
    

All Problems

All Solutions