[Python知识库]2021-08-14:字符串数组问题：

?解题思路：

1.hashmap:? ? ?hashmap = defaultdict(int)

2.循环字符串：把前后字符串拼在一起

3.反转字符串? a = b [::-1]

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dict1 = defaultdict(int)
        dict2 = defaultdict(int)
        for s1 in s:
            dict1[s1] += 1
        for s2 in t:
            dict2[s2] += 1
        return dict1 ==dict2

暴力破解法：时间复杂度N^2，超时了

class Solution:
    def countSubstrings(self, s: str) -> int:
        l = len(s)
        print(l)
        ans = 0
        for i in range(l):
            for j in range(i+1,l+1):
                string = s[i:j]
                print(string)
                if self.Isomorphic(string):
                    ans += 1
        return ans
    def Isomorphic(self,s):
        return s == s[::-1]

方法2：回文中心法：

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        ans = 0
        for i in range(2*n-1):
            left = i // 2 
            right = left + i % 2
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1
                ans += 1
        return ans

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x == 0:
            return True
        if x < 0 or x % 10 == 0:
            return False
        right = 0
        while(x > right):
            right = right * 10 + x % 10
            x = x // 10
        return x == right or right // 10 == x
        

思路：

定中心位置后向两边延申：

python 异或符号 ^?

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        n = len(s)
        cnt = 0
        for i in range(n-1):
            left = i
            right = i+1
            while left >= 0 and right <n:
                string = s[left:right+1]
                
                zero = string.count('0')
                one = string.count('1')
                if zero == one:
                    print(left,right, string)
                    cnt += 1
                left -= 1
                right += 1
                if left < 0 or right >= n or s[left] != s[left+1] or s[right] != s[right -1]:
                    break
        return cnt

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        n = len(s)
        cnt = 0
        for i in range(n-1):
            left = i
            right = i+1
            if int(s[left]) ^ int(s[right]) == 1:
                while left>=0 and right < n:
                    if s[left] == s[i] and s[right] == s[i+1]:
                        cnt += 1
                        left -= 1
                        right += 1
                    else:
                        break
        return cnt

?