LeetCode_排序_双指针_中等_524.通过删除字母匹配到字典里最长单词

深藏阁楼爱情的钟 2023-10-06 23:49 22阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

**示例 1：**  
输入：s = “abpcplea”, dictionary = \[“ale”,“apple”,“monkey”,“plea”\]  
输出：“apple”

**示例 2：**  
输入：s = “abpcplea”, dictionary = \[“a”,“b”,“c”\]  
输出：“a”

**提示：**  
1 <= s.length <= 1000  
1 <= dictionary.length <= 1000  
1 <= dictionary\[i\].length <= 1000  
s 和 dictionary\[i\] 仅由小写英文字母组成

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting

## 2.思路 ##

（1）排序 & 判断子序列  
有关**判断子序列**的问题可以参考[LeetCode\_双指针\_二分搜索\_简单\_392.判断子序列][LeetCode_392.]这篇文章，此处不再赘述。

① 先对 dictionary 进行自定义排序，排序规则如下：  
1）先按字符串长度进行降序排序；  
2）如果长度相等，再按字典序降序排序；

② 定义 res 和 maxLen，其初始值分别为 “” 和 0，分别用于保存最终结果以及结果的最大长度；

③ 开始遍历 dictionary：  
1）如果当前字符串 dic 的长度大于等于 maxLen，并且 dic 是 s 的子序列，那么更新 maxLen 和 res；  
2）如果 dic 的长度小于 maxLen，那么则说明 maxLen 和 res 已经至少被更新过一次（换言之，即已经尽可能地**找到了长度最长且是 s 的子序列的字符串**），并且该字符串以及后面的字符串无需再判断，可直接结束遍历；

④ 遍历结束后直接返回 res 即可。

## 3.代码实现（Java） ##

//思路1————排序 & 判断子序列
    class Solution {
        
        public String findLongestWord(String s, List<String> dictionary) {
        
            /*
                自定义排序规则：
                (1) 先按字符串长度进行降序排序
                (2) 如果长度相等，再按字典序降序排序
            */
            dictionary.sort((d1, d2) -> {
        
                if (d1.length() != d2.length()) {
        
                    return d2.length() - d1.length();
                } else {
        
                    return d2.compareTo(d1);
                }
            });
            String res = "";
            // maxLen 保存 dictionary 中符合题目条件的字符串的最大长度
            int maxLen = 0;
            for (String dic : dictionary) {
        
                if (dic.length() >= maxLen && isSubsequence(dic, s)) {
        
                	//更新 maxLen 和 res
                    maxLen = dic.length();
                    res = dic;
                }
                //如果当前字符串的长度小于 maxLen，那么说明该字符串以及后面的字符串无需再判断，直接结束遍历即可
                if (dic.length() < maxLen) {
        
                    break;
                }
            }
            return res;
        }
        
        /*
            判断 s 是否为 t 的子序列
            代码参考【LeetCode_392.判断子序列】
        */
        public boolean isSubsequence(String s, String t) {
        
            //定义双指针 i 和 j
            int i = 0, j = 0;
            int sLen = s.length(), tLen = t.length();
            //分别遍历 s 和 t
            while (i < sLen && j < tLen) {
        
                if (s.charAt(i) == t.charAt(j)) {
        
                    i++;
                }
                j++;
            }
            return i == sLen;
        }
    }

[LeetCode_392.]: https://blog.csdn.net/weixin_43004044/article/details/122371821