华为一面\华为主管面 手撕代码题目

原题链接:
https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 贪心 + 双指针
 删除某些字母得到 = 该单词为字符串s的子序列 且 是有序的

 按照长度排序 那么最先匹配完成的就是就是符合答案的
 题目又要求字典序最小 那就再按照字典序进行排序
 */

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        /*
        * compareTo 相等返回 0
        *           小于返回 -1
        *           大于返回 1
        * */
        Collections.sort(dictionary,(o1,o2)->{
            if(o1.length() == o2.length()){
                return o1.compareTo(o2);
            }
            return o2.length() - o1.length();
        });
        int n = s.length();
        for (var ss: dictionary){
            int m = ss.length();
            int i = 0, j = 0;
            while (i < n && j < m){
                if(s.charAt(i) == ss.charAt(j)){
                    j++;
                }
                i++;
            }
            if (j == m){
                return ss;
            }
        }

        return "";
    }
}