Krahets88道 哈希表

有效的字母异位词

Problem: 242. 有效的字母异位词

思路

单词循环逐个对比各个字符串

解题方法

利用两个指针查找，指针一不变，指针二在字符串二中不断向后，如无相同字符则返回False，反之就删除找到的相同字符。

复杂度

时间复杂度:

添加时间复杂度, 示例： O(n)

空间复杂度:

添加空间复杂度, 示例： O(n)

Code

from collections import defaultdict

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        """判断两个字符串是否是异位词-自己的解法"""
        i, j = 0, 0
        if len(s) != len(t):
            return False
        while s != '':
            if s[i] == t[j]:
                s = s[1:]
                t = t[:j] + t[j+1:]
                j = 0
            elif j == len(t)-1:
                return False
            else:
                j += 1
        return s == ''
    
    def isAnagramK(self, s: str, t: str) -> bool:
        """判断两个字符串是否是异位词-Krahets解法"""
        if len(s) != len(t):
            return False
        dic = defaultdict(int)
        for c in s:
            dic[c] += 1
        for c in t:
            dic[c] -= 1
        # 判断字典中的值是否都为0
        for v in dic.values():
            if v != 0:
                return False
        return True

sol = Solution()

res = sol.isAnagram('rat','cad')

print(res)

字符串中的第一个唯一字符

Problem: 387. 字符串中的第一个唯一字符

思路

使用哈希表存储每个字符出现的次数，然后再次循环找到出现次数为1的字符的下标

解题方法

我首先用了一个int类型的defaultdict存储每个字符出现的次数，然后用另一个defaultdict存储了各个字符的下标

问题在于

1. 本题不关心字符出现了多少次，只关心字符是否只出现了一次，第一个哈希表不应使用int类型的defaultdict，用普通字典存储是否为第一次的布尔值即可
2. 字符的下表即在字符串中，无需特地去用字典存储起来，只需将第二次循环的数据源改为 enumerate即可。

复杂度

时间复杂度:

添加时间复杂度, 示例： O(n)

空间复杂度:

添加空间复杂度, 示例： O(n)

Code

from collections import defaultdict

class Solution:
    
    def firstUniqChar(self, s: str) -> int:
        """字符串中的第一个唯一字符-自己的解法"""
        dic = defaultdict(int)
        dicIndex = defaultdict(int)
        for i,c in enumerate(s):
            dic[c] += 1
            dicIndex[c] = i
        for k,v in dic.items():
            if v == 1:
                return dicIndex[k]
        return -1
    
    def firstUniqCharK(self, s: str) -> int:
        """字符串中的第一个唯一字符-Krahets解法"""
        # 初始化字典
        # 字符统计
        # 查找数量为1的字符的下标
        dic = {}
        for c in s:
            dic[c] = not c in dic
        for i, c in enumerate(s):
            if dic[c]: return i
        return -1
    
sol = Solution()

res = sol.firstUniqChar('loveleetcode')

print(res)

同构字符串

Problem: 205. 同构字符串

思路

使用一个哈希表记录两字符串的映射关系，通过判断key和value是否存在决定是否为同构字符串。

解题方法

通过一轮循环，将s_char记为key，t_char记为value

当s_char存在哈希表中，但其value(t_char)与t_char不一致时，不为同构字符串。 当t_char存在哈希表中，但s_char并没有作为key存在于哈希表中时，不为同构字符串。

这个方法只用到一个哈希表，空间小，时间一般，相当于用时间换空间

复杂度

时间复杂度:

添加时间复杂度, 示例： O(n)

空间复杂度:

添加空间复杂度, 示例： O(1)

Code

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        """同构字符串"""
        if len(s) != len(t):
            return False
        dic = {}
        for s_char, t_char in zip(s, t):
            # key在字典中，value不同
            if s_char in dic and dic[s_char] != t_char:
                return False
            # value在字典中，key不同
            elif t_char in dic.values() and s_char not in dic:
                return False
            dic[s_char] = t_char
        return True

最长回文串

Problem: 409. 最长回文串

思路

用哈希表记录字符出现次数（仅偶数） 如果有任意奇数则额外 + 1

解题方法

将字符出现次数最大偶数相加，如果存在奇数则额外 + 1

复杂度

时间复杂度:

添加时间复杂度, 示例： O(n)

空间复杂度:

添加空间复杂度, 示例： O(1)

Code

class Solution:
    def longestPalindrome(self, s: str) -> int:
        """
        最长回文串
        思路：用哈希表记录字符出现次数（仅偶数）
             如果有任意奇数则额外 + 1
        """
        res = 0
        ad = False
        if not s:
            return False
        dic = {}
        dic = defaultdict(int)
        for c in s:
            dic[c] += 1
        for c in dic.values():
            res += c // 2 * 2
            if ~ad and c % 2 == 1:
                ad = True
        if  ad:
            res += 1
        return res