648. Word replacement

648. Word substitution 【 Medium question 】【 A daily topic 】

Ideas ：

Sort the word roots by length
Traverse each word , For the current word , Traverse the root list , Filter out the prefix of the first word in the root , And update the current word with this prefix .
Finally, all the updated words are separated by spaces and spelled into strings to return .

Code ：

class Solution {
    
    public String replaceWords(List<String> dictionary, String sentence) {
    
        // Sort root dictionaries by length 
        dictionary.sort(Comparator.comparingInt(String::length));
        // Divide sentences into spaces 
        String[] words = sentence.split(" ");
        int n = words.length;
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; i++) {
    // Traverse each word in the word array 
            // Record the length of the current word 
            int word_n = words[i].length();
            // Traverse the root dictionary , Filter out the first prefix of the current word and update it to the current position of the word array 
            for (String prefix : dictionary) {
    
                // Record the current root length 
                int pre_n = prefix.length();
                // If the root length is greater than the word , Then it cannot be a prefix , Because the root list is sorted from small to large according to the length , Therefore, the current root length is greater than the word , Then there is no need to continue the cycle , The length of the trailing root is greater than that of the word , Therefore, the current word has no prefix in the root dictionary , Words remain the same 
                // If the root length is equal to the word , If the root word is equal to the word , Then update the word to root , Equivalent to constant ; If the root word is not equal to the word , Then the words remain the same 
                // Sum up , Root length  >=  Word length , Words remain the same , It can be understood as   There is no prefix in the root dictionary 
                if (pre_n >= word_n){
    
                    break;
                }
                // At this time, the root length must be less than the word length , If the root word is the prefix of the word , Then update the word with a prefix , Because the title requires to replace with the shortest root , So the loop exits 
                if (words[i].startsWith(prefix)){
    
                    words[i] = prefix;
                    break;
                }
                // If the root is not the prefix of the word , Then continue to cycle through the next root 
            }
            // The processed words   Append to  ans Back , And append spaces 
            ans.append(words[i]).append(" ");
        }
        // take ans Turn it into a string and remove the trailing space, and then return 
        return ans.toString().trim();
    }
}