Welcome to Subscribe On Youtube

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;
    }
};
  • 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];
        }
    }
    
    ############
    
    class Trie {
        Trie[] children = new Trie[26];
        String v;
    
        void insert(String word) {
            Trie node = this;
            for (char c : word.toCharArray()) {
                c -= 'a';
                if (node.children[c] == null) {
                    node.children[c] = new Trie();
                }
                node = node.children[c];
            }
            node.v = word;
        }
    
        String search(String word) {
            Trie node = this;
            for (char c : word.toCharArray()) {
                c -= 'a';
                if (node.children[c] == null) {
                    return word;
                }
                node = node.children[c];
                if (node.v != null) {
                    return node.v;
                }
            }
            return word;
        }
    }
    
    class Solution {
        public String replaceWords(List<String> dictionary, String sentence) {
            Trie trie = new Trie();
            for (String v : dictionary) {
                trie.insert(v);
            }
            List<String> ans = new ArrayList<>();
            for (String v : sentence.split("\\s")) {
                ans.add(trie.search(v));
            }
            return String.join(" ", ans);
        }
    }
    
  • // 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 Trie:
        def __init__(self):
            self.children = [None] * 26
            self.v = None
    
        def insert(self, word):
            node = self
            for c in word:
                idx = ord(c) - ord('a')
                if node.children[idx] is None:
                    node.children[idx] = Trie()
                node = node.children[idx]
            node.v = word
    
        def search(self, word):
            node = self
            for c in word:
                idx = ord(c) - ord('a')
                if node.children[idx] is None:
                    break
                node = node.children[idx]
                if node.v:
                    return node.v
            return word
    
    
    class Solution:
        def replaceWords(self, dictionary: List[str], sentence: str) -> str:
            trie = Trie()
            for v in dictionary:
                trie.insert(v)
            return ' '.join(trie.search(v) for v in sentence.split())
    
    ############
    
    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)
    
    
  • type Trie struct {
    	children [26]*Trie
    	v        string
    }
    
    func newTrie() *Trie {
    	return &Trie{}
    }
    func (this *Trie) insert(word string) {
    	node := this
    	for _, c := range word {
    		c -= 'a'
    		if node.children[c] == nil {
    			node.children[c] = newTrie()
    		}
    		node = node.children[c]
    	}
    	node.v = word
    }
    
    func (this *Trie) search(word string) string {
    	node := this
    	for _, c := range word {
    		c -= 'a'
    		if node.children[c] == nil {
    			break
    		}
    		node = node.children[c]
    		if node.v != "" {
    			return node.v
    		}
    	}
    	return word
    }
    
    func replaceWords(dictionary []string, sentence string) string {
    	trie := newTrie()
    	for _, v := range dictionary {
    		trie.insert(v)
    	}
    	var ans []string
    	for _, v := range strings.Split(sentence, " ") {
    		ans = append(ans, trie.search(v))
    	}
    	return strings.Join(ans, " ")
    }
    
  • class Trie {
        private children: Trie[];
        private ref: number;
    
        constructor() {
            this.children = new Array<Trie>(26);
            this.ref = -1;
        }
    
        public insert(w: string, i: number) {
            let node: Trie = this;
            for (const c of w) {
                const idx = c.charCodeAt(0) - 97;
                if (!node.children[idx]) {
                    node.children[idx] = new Trie();
                }
                node = node.children[idx];
            }
            node.ref = i;
        }
    
        public search(w: string): number {
            let node: Trie = this;
            for (const c of w) {
                const idx = c.charCodeAt(0) - 97;
                if (!node.children[idx]) {
                    return -1;
                }
                node = node.children[idx];
                if (node.ref !== -1) {
                    return node.ref;
                }
            }
            return -1;
        }
    }
    
    function replaceWords(dictionary: string[], sentence: string): string {
        const trie = new Trie();
        for (let i = 0; i < dictionary.length; i++) {
            trie.insert(dictionary[i], i);
        }
        return sentence
            .split(' ')
            .map(w => {
                const idx = trie.search(w);
                return idx !== -1 ? dictionary[idx] : w;
            })
            .join(' ');
    }
    
    

All Problems

All Solutions