648. Replace Words (Medium)

https://leetcode.com/problems/replace-words/

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

 

Solutions

class Solution {

    public String replaceWords(List<String> dict, String sentence) {
        Trie root = new Trie();
        for (String w : dict) {
            root.add(0, w);
        }

        String ans = "";
        String[] words = sentence.split(" ");
        for (String w : words) {
            String wx = retrieve(root, w);

            ans += wx + " ";
        }

        // trim off the last blank space
        return ans.trim();
    }

    private String retrieve(Trie root, String word) {
        String ans = "";

        // pointer of scanning sub tries
        Trie trie = root;

        // Flag variable, false means the given word does not have any root sequence,
        // true means found in the root trie.
        boolean isFound = false;

        for (int i = 0; i < word.length(); i++) {
            trie = trie.get(word.charAt(i));

            // reach the end and not found desired root sequence
            if (trie == null) {
                break;
            }

            ans += word.charAt(i);

            // Exists related root sequence with this word in the dictionary.
            if (trie.word != null) {
                isFound = true;

                break;
            }
        }

        if (!isFound) {
            ans = word;
        }

        return ans;
    }

    private class Trie {

        // From the root Trie node to current one, if the letter sequence forms a word
        // existing in the dictionary, then set the word to this variable. Otherwise,
        // current sub Trie is not the end of any words in the dictionary and remains null;
        String word = null;

        // Used to keep sub tries
        Map<Character, Trie> subTries = new HashMap<>();

        public void add(int i, String word) {
            if (i == word.length()) {
                this.word = word;

                return;
            }

            Character c = word.charAt(i);
            if (!subTries.containsKey(c)) {
                subTries.put(c, new Trie());
            }

            // Add the letters to sub tries recursively.
            subTries.get(c).add(i+1, word);
        }

        public Trie get(Character c) {
            return subTries.get(c);
        }
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""