LeetCode-字符串1

[MiaoRain]

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dic = {}
        for char in s:
            dic[char] = dic.get(char, 0) + 1
        #print(dic)
        for char1 in t:
            if char1 in dic:
                dic[char1] -= 1
            else:
                return False
        for val in dic.values():
            if val != 0:
                return False
        return True

[MiaoRain]

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list)#字典中的值，用list表示
        #ans = {}#普通字典，输入新的key，会报错，上面方式就可以解决
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            #print(count)
            #print(tuple(count))
            ans[tuple(count)].append(s)
            #print(ans)#{(1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0): ['eat']})
        return ans.values()

[MiaoRain]

'''
        解法1：滑动窗口
        '''
        res = []
        window = {}     # 记录窗口中各个字符数量的字典
        needs = {}      # 记录目标字符串中各个字符数量的字典
        for c in p: needs[c] = needs.get(c, 0) + 1  # 统计目标字符串的信息

        length, limit = len(p), len(s)
        left = right = 0                    # 定理两个指针，分别表示窗口的左、右界限

        while right < limit:
            c = s[right]
            if c not in needs:              # 当遇到不需要的字符时
                window.clear()              # 将之前统计的信息全部放弃
                left = right = right + 1    # 从下一位置开始重新统计
            else:
                window[c] = window.get(c, 0) + 1            # 统计窗口内各种字符出现的次数
                if right-left+1 == length:                  # 当窗口大小与目标字符串长度一致时
                    if window == needs: res.append(left)    # 如果窗口内的各字符数量与目标字符串一致就将left添加到结果中
                    window[s[left]] -= 1 
                    left += 1                               # left右移
                                       # 并将移除的字符数量减一
                right += 1                                  # right右移
        return res

[MiaoRain]

left = 0
        right = len(s) - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            
            if s[left].lower() != s[right].lower():
                return False
            else:
                left += 1
                right -= 1
        return True

[MiaoRain]

class Solution:
    def validPalindrome(self, s: str) -> bool:
        #double points
        left = 0
        print(s[1:2])
        right = len(s) - 1
        while left < right:
            if s[left] != s[right]:
                #print(left, right)
                one, two = s[left:right], s[left +1:right +1]
                #print(one, two)
                return one == one[::-1] or two == two[::-1]
            left += 1
            right -= 1
        return True

[MiaoRain]

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        if not head: return None
        p = head
        stack = []
        # 把所有节点压入栈中
        while p:
            stack.append(p)
            p = p.next
        # 长度
        n = len(stack)
        # 找到中点前一个位置 
        count = (n - 1) // 2
        p = head
        while count:
            # 弹出栈顶
            tmp = stack.pop()
            # 与链头拼接
            tmp.next = p.next
            p.next  = tmp
            # 移动一个位置
            p = tmp.next
            count -= 1
        stack.pop().next = None

[MiaoRain]

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        #删除，插入， 替换
        n1 = len(word1)
        n2 = len(word2)
        dp = [[0]*(n2 + 1) for _ in range(n1 + 1)] #建立一个二维矩阵
        #first row
        for j in range(1, n2 + 1):
            dp[0][j] = dp[0][j-1] + 1
        
        #first column
        for i in range(1, n1 + 1):
            dp[i][0] = dp[i-1][0] + 1
            
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
        #print(dp)
        return dp[-1][-1]

[MiaoRain]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ""
        # 枚举子串的长度 l+1
        for l in range(n):
            # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置
            for i in range(n):
                j = i + l
                if j >= len(s):
                    break
                if l == 0:
                    dp[i][j] = True
                elif l == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
                if dp[i][j] and l + 1 > len(ans):
                    ans = s[i:j+1]
        return ans

[MiaoRain]

return len(set(s)) == len(set(zip(s,t))) == len(set(t))