字符串面试题 python

字符串中单词的翻转。将每个单词翻转，然后将整个字符串翻转。 s = "I am a student" Return "student a am I" 两个字符串包含的字符是否完全相同 方法1：字典： class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ if len(s) != len(t): return False d_s = {} d_t = {} for c in s: d_s[c] = d_s.get(c,0)+1 for c in t: d_t[c] = d_t.get(c,0)+1 if d_s == d_t: return True else: return False

方法2：

import collections class Solution: def isAnagram(self, s: str, t: str) -> bool: return collections.Counter(s) == collections.Counter(t) 计算一组字符集合可以组成的回文字符串的最大长度 class Solution: def longestPalindrome(self, s: str) -> int: odd, res = 0, 0 d = {} for c in s: d[c] = d.get(c, 0) + 1 for key in d: if d[key] % 2 == 0: res += d[key] else: res += d[key]-1 odd = 1 return res if odd == 0 else res + 1 字符串同构 思路：用一个字典来统计字符及对应的数值。主要比较列表是否相同。 class Solution: def isIsomorphic(self, s: str, t: str) -> bool: # 如：paper：list_s=[1,2,1,3,4] d = {} list_s = [] new = 1 for c in s: if c in d: list_s.append(d[c]) else: d[c] = new list_s.append(new) new += 1 d = {} list_t = [] new = 1 for c in t: if c in d: list_t.append(d[c]) else: d[c] = new list_t.append(new) new += 1 return list_s == list_t 回文子字符串个数 暴力法： class Solution: def countSubstrings(self, s: str) -> int: n = len(s) res = 0 for i in range(0,n): for j in range(i+1,n+1): if s[i:j] == s[i:j][::-1]: res += 1 return res

动态规划

class Solution: def countSubstrings(self, s: str) -> int: # 时间复杂度：O（N^2）,空间复杂度：O（N^2） n = len(s) if n == 0: return 0 res = 0 dp = [[False for _ in range(n)] for _ in range(n)] for i in range(n): dp[i][i] = True for j in range(n): # 先有了i的状态才能有i+1的状态，所以此处遍历以j为主 for i in range(0, j): if j - i == 1: if s[i] == s[j]: dp[i][j] = True else: if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] for i in range(n): for j in range(i, n): if dp[i][j] is True: res += 1 return res 判断一个整数是否是回文数（不能使用额外空间，即不能将整数转为字符串进行判断。） class Solution: def isPalindrome(self, x: int) -> bool: n = 0 x1=x if x<0: return False while x1: n = n*10+x1%10 x1 = x1//10 return n==x 统计二进制字符串中连续 1 和连续 0 数量相同的子字符串个数 Input: "00110011" Output: 6 Explanation:"0011", "01", "1100", "10", "0011", and "01". class Solution: def countBinarySubstrings(self, s: str) -> int: # 计数分割字符串。如00110分割为counts = [2, 2, 1]，再对counts两两取最小值求和即为结果。 seq0, seq1 = 0, 1 # seq0记前面的数的连续数,seq1记当前数的连续数。上一个连续数是0个，现在的连续数为1。 res = 0 for i in range(1, len(s)): if s[i] == s[i-1]: seq1 += 1 # 第一次循环0==0，当前连续数+1，所以seq1=2 else: res += min(seq0, seq1) # 第二次循环0!=1，当前连续数终止，前一连续数与当前连续数最小值0作为结果。 seq0 = seq1 seq1 = 1 res += min(seq0, seq1) return res