[daily training] 648 Word replacement

subject

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⁶
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 .

Code

package dayLeetCode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class dayleetcode648 {
    
    //  simulation   Pay attention to set Otherwise, the time limit will be exceeded 
    public String replaceWords(List<String> dictionary, String sentence) {
    
        Set<String> set = new HashSet<>();
        for (String str : dictionary){
    
            set.add(str);
        }


        String[] s = sentence.split(" ");
// StringBuffer ansStr = new StringBuffer();
        for (int j = 0; j < s.length; j++){
    
            //  From the beginning of each word   Be afraid to break the word root with or without giving 
            String str = s[j];
           for (int i = 0; i < str.length(); i++){
    
               if (set.contains(str.substring(0, i))){
    
                   s[j] = str.substring(0, i);
                   break;
               }
           }
// if (j == s.length - 1){
    
// ansStr.append(s[j]);
// }
// else{
    
// ansStr.append(s[j] + " ");
// }
        }

        return String.join(" ", s);
    }

    public static void main(String[] args) {
    
        dayleetcode648 obj = new dayleetcode648();
        List<String> dict = new ArrayList<>();
        dict.add("cat");
        dict.add("bat");
        dict.add("rat");
        String str = "the cattle was rattled by the battery";
        System.out.println(obj.replaceWords(dict, str));
    }
}