648. 单词替换

648. 单词替换【中等题】【每日一题】

思路：

将词根按长度进行排序后
遍历每个单词，对当前单词，遍历词根列表，筛选出词根中第一个单词前缀，并将当前单词更新为这个前缀。
最后将所有更新过的单词用空格分隔拼成字符串返回即可。

代码：

class Solution {
    
    public String replaceWords(List<String> dictionary, String sentence) {
    
        //对词根词典按长度排序
        dictionary.sort(Comparator.comparingInt(String::length));
        //将句子按空格切分
        String[] words = sentence.split(" ");
        int n = words.length;
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; i++) {
    //遍历单词数组中每个单词
            //记录当前单词的长度
            int word_n = words[i].length();
            //遍历词根字典，筛选出当前单词的第一个前缀并将其更新到单词数组的当前位置
            for (String prefix : dictionary) {
    
                //记录当前词根长度
                int pre_n = prefix.length();
                //如果词根长度大于单词，则其不可能为前缀，由于词根列表根据长度从小到大排序，因此当前词根长度大于单词，那么后续就不用继续循环了，后边词根长度全部大于单词，因此当前单词无在词根字典中的前缀，单词保持不变
                //如果词根长度等于单词，那假如词根与单词相等，那么单词更新为词根，相当于不变；假如词根与单词不相等，那么单词依然保持不变
                //综上，词根长度 >= 单词长度时，单词保持不变，可以理解为 没有在词根词典中的前缀
                if (pre_n >= word_n){
    
                    break;
                }
                //此时词根长度一定小于单词长度，如果词根是单词的前缀，那么将单词更新为前缀，由于题目要求用最短的词根替换，因此循环退出
                if (words[i].startsWith(prefix)){
    
                    words[i] = prefix;
                    break;
                }
                //如果词根不是单词的前缀，则继续循环筛选下一个词根
            }
            //将处理过的单词 追加到 ans后边，并追加空格
            ans.append(words[i]).append(" ");
        }
        //将ans转为字符串并去掉尾部空格后返回
        return ans.toString().trim();
    }
}