算法随笔_23: 通过删除字母匹配到字典里最长单词

上一篇:算法随笔_22:数组中的k-diff对-CSDN博客

======

题目描述如下:

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

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

示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

======

算法思路:

根据题目要求，我们可以枚举dictionary里的每个字符串str1，判断str1是否可以通过删除 s 中的某些字符得到。在所有匹配到的str1中选出长度最大的那个。如果长度一样，选出字母序最小的那个。如果使用Python语言，两个字符串比较大小是基于字典顺序进行的，较小的字符串就是字母序最小的那个。

算法现在还剩一个问题，就是如何判断str1是否可以通过删除 s 中的某些字符得到？

首先能想到的还是暴力解法，两层循环，分别枚举str1和s字符串，比较两个字符是否一样，最终得出结论。由于算法的最外层还有一层枚举dictionary，所以这样算法时间复杂度很高了，我们需要考虑一下如何优化它。

经过进一步的分析，我们发现，如果枚举完str1的第一个元素，并且在s的下标p2处找到了相同的字符时，当开始枚举str1的第二个元素时，我们不需要从s的下标0处开始匹配，我们只需要从p2+1处开始匹配。因为题目是要求删除s中的字符来得到字符串str1，因此，s剩下的字符之间的顺序是不变的。str1的第二个元素必然要从s的p2+1处开始寻找。这样就简化了很多的重复寻找。因此对于问题"判断str1是否可以通过删除 s 中的某些字符得到"，我们可以给出下面的算法:

设两个指针p1，p2，分别指向字符串s和str1的起始处。设match_cnt为字符匹配数。

如果两个字符相同，我们右移p2指针，且对match_cnt加1。

不管两个字符是否相同，我们都需要访问s的下一个元素，所以我们需要右移p1指针。

当p1或p2任意一个指针到达字符串末尾时，我们退出循环。如果match_cnt等于str1字符串的长度，就表示我们找到了一个符合条件的字符串。

为了节省空间，我们可以对整个算法再做一个小小的优化。我们不需要把符合条件的字符串存入数组当中。我们只需把当前的结果与先前的结果res_str做一个比较。如果当前结果的字符串的长度比先前结果res_str的长度长，我们就替换res_str。长度相同的条件下，如果字母序更小，我们也替换字符串res_str。

下面为代码实现:

class Solution(object):
    def findLongestWord(self, s, dictionary):
        """
        :type s: str
        :type dictionary: List[str]
        :rtype: str
        """
        res_str=""
        for str1 in dictionary:
            p1=0
            p2=0
            match_cnt=0
            
            s_len=len(s)
            str1_len=len(str1)
            while p1 < s_len and p2 < str1_len:
                if s[p1]==str1[p2]:
                     match_cnt+=1
                     p2+=1
                p1+=1
            if match_cnt==str1_len:
                if len(res_str)<str1_len:
                    res_str=str1
                elif len(res_str)==str1_len:
                    if res_str>str1:
                        res_str=str1
        return res_str