力扣(leetcode) 748. 最短补全词 (双指针法) (哈希表法)

题目在这:​​https://leetcode-cn.com/problems/shortest-completing-word/​​

法一:(双指针)

这道题不难，就是比较恶心。 按下面的思路一步一步写就行了。

• 全部变为小写
• 排序(此步骤已除去中间空格)
• 变为字符串并除去前后空格
• 使用正则提取所有小写字母
• 设置两个指针，s指向licensePlate串，j指向words串中的每个单词。如果两指针指向元素相等，则s和j都往后挪。如果不相等则j往后挪。
• 如果s遍历到最后了则说明算一个补全单词，加入到res，如果是j遍历到最后了，则不是补全单词，重置j=0 s=0 ，继续遍历一下一个words里的单词。
• 得到res后判断res中是否只有一个元素，如果是则直接返回，如果不是则找最长的且第一个出现的字符。

完整代码

代码写的比较乱，边调试边写的，参考一下就行。按上面思路写就行。

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        import re
        def A(licensePlate,words,res):
            licensePlate = licensePlate.lower()
            licensePlate = sorted(licensePlate)
            licensePlate = ''.join(licensePlate).strip()
            licensePlate = re.search('[a-z]+',licensePlate)
            licensePlate = licensePlate.group()
            for i in words:
                s = 0
                j = 0
                temp = i
                i = i.lower()
                i = sorted(i)
                i = ''.join(i).strip()
                while True:
                    if licensePlate[s] == i[j]:
                        s +=1
                    j +=1
                    if s == len(licensePlate):
                        res.append(temp)
                        break
                    if j == len(i):
                        break
 
        res = []
        A(licensePlate,words,res)
        print()
        if len(res) == 1:
            return ''.join(res)
        length = len(res[0])
        ans = res[0]
        for p in res:
            if len(p) < length:
                length = len(p)
                ans = p # 记录最小长度 第一个出现的单词
        print(ans)
        return      

法二:(哈希表法)

和上面的思路差不多，只不过在双指针对比的时候改成哈希表对比。

licensePlate串建立哈希表A。 key存元素，value存该元素出现的次数。

words串建立哈希表B。

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:    
        from collections import Counter
        import re
        licensePlate = licensePlate.lower()
        licensePlate = sorted(licensePlate)
        licensePlate = ''.join(licensePlate).strip()
        licensePlate = re.search('[a-z]+',licensePlate)

        licensePlate = licensePlate.group()
        print(licensePlate)
        hash_licen = Counter(licensePlate)

        print(hash_licen)
        res = []


        for i in words:
            bol = True
            hash_i = Counter(i)
            for j in hash_licen:
                if j not in hash_i:
                    bol = False
                    break
                if hash_i[j] < hash_licen[j]:
                    bol = False
                    break
            if bol:
                res.append(i)

        print("这里是res",res)
        if len(res) == 1:
            return ''.join(res)


        length = len(res[0])
        ans = res[0]
        for p in res:
            if len(p) < length:
                length = len(p)
                ans = p # 记录最小长度 第一个出现的单词
        return ''.join(ans)