Replace Words

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

In English, we have a concept calledroot, which can be followed by some other words to form another longer word - let's call this wordsuccessor. For example, the rootan, followed byother, which can form another wordanother.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all thesuccessorin the sentence with therootforming it. If asuccessorhas manyrootscan form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Thoughts

直观的想法，把每个单词的可能prefix找出来，看是否在dict里。

Code

class Solution {
    public String replaceWords(List<String> dict, String sentence) {
        Set<String> set = new HashSet<>();
        for (String str : dict) {
            set.add(str);
        }
        StringBuilder sb = new StringBuilder();
        for (String str : sentence.split(" ")) {
            boolean found = false;
            for (int i = 1; i <= str.length(); i++) {
                String sub = str.substring(0 , i);
                if (set.contains(sub)) {
                    sb.append(sub);
                    found = true;
                    break;
                }
            }
            if (!found) {
                sb.append(str);
            }
            sb.append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
}

Analysis

时间复制度O(n), n为总字符数。