Force deduction solution summary 648 word replacement

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

In English , We have one called   Root (root) The concept of , You can add other words after the root to form another longer word —— We call it   Inheritance words (successor). for example , Root an, Follow the word  other( other ), Can form new words  another( the other one ).

Now? , Given a dictionary consisting of many roots dictionary And a sentence formed by separating words with spaces sentence. You need to replace all the inherited words in the sentence with roots . If an inherited word has many roots that can form it , Replace it with the shortest root .

You need to output the replaced sentences .

Example 1：

Input ：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output ："the cat was rat by the bat"
Example 2：

Input ：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output ："a a b c"
 

Tips ：

1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i]  It's only made up of lowercase letters .
1 <= sentence.length <= 10^6
sentence  Only lowercase letters and spaces .
sentence The total number of words in the range [1, 1000] Inside .
sentence The length of each word in the range [1, 1000] Inside .
sentence Words in are separated by a space .
sentence  No leading or trailing spaces .
 

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/replace-words
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  Use Set Storage dictionary The characters in , Then traverse sentence The characters in , Each character takes its own 1,2,3,4,length The length of , see set Whether there is .

Code ：

public class Solution648 {

    public String replaceWords(List<String> dictionary, String sentence) {
        Set<String> set = new HashSet<>(dictionary);
        String[] strings = sentence.split(" ");
        for (int i = 0; i < strings.length; i++) {
            String str = strings[i];
            for (int k = 1; k < str.length(); k++) {
                String substring = str.substring(0, k);
                if (set.contains(substring)) {
                    str = substring;
                    break;
                }
            }
            strings[i] = str;
        }
        return String.join(" ", strings);
    }
}