classSolution: defmergeAlternately(self, word1: str, word2: str) -> str: ans = [] m, n = len(word1), len(word2) for i inrange(min(m,n)): ans.append(word1[i]) ans.append(word2[i]) if m >= n: ans.extend(word1[n:]) else: ans.extend(word2[m:]) return"".join(ans) """ 先创建两个整型变量用于存储字符串的长度 后循环其中较小的数的次数,依次添加字符进列表 相同长度的字符串添加后,进行条件判断,添加剩余的未被添加的字符 """
classSolution: deffindTheDifference(self, s: str, t: str) -> str: ans = 0 for i in s: ans ^= ord(i) for i in t: ans ^= ord(i) returnchr(ans) # 由于s与t字符串只差了一个字符,可以使用异或运算将所有相同的字符串抵消,最终剩下的那个就是多出的字符
解法2-单字符Count()查不同
1 2 3 4 5 6
classSolution: deffindTheDifference(self, s: str, t: str) -> str: for c in t: if t.count(c) != s.count(c): return c # 使用count来统计字符串中含有对应字符的数量,如果不一致,则为多出的字符
解法3-哈希表
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution: deffindTheDifference(self, s: str, t: str) -> str: cnt = [0] * 26 for ch in s: cnt[ord(ch) - 97] += 1 for ch in t: idx = ord(ch) - 97 cnt[idx] -= 1 if cnt[idx] < 0: return ch # 认识到小写英文字符只有26个,创建包含26个空列表的列表cnt # 循环s中的字符ch,对其计数。注意这里使用ord(ch) - 97的方法写下标赋值 # 循环t中的字符ch,出现一次就对cnt中对应的值-1,第一次出现负数所对应的下标即为新增字符
classSolution: defstrStr(self, haystack: str, needle: str) -> int: m, n = len(haystack), len(needle) if m < n: return -1 for i inrange(m - n + 1): for j inrange(n): if haystack[i + j] != needle[j]: break if j == n - 1: return i return -1 # 先去定义两个整型变量用于存储两个字符串的长度 # 开头校验,如果needle字符串的长度大于haystack,则直接返回-1 # 循环读取字符串hatstack下标[0, m - n] # 嵌套循环从对应下标i处进行条件判断,字符是否一致,若不一致则break,从下一个下标出再次判断 # 若都一致-即从头到最后都没有break出去的话,则包含,返回下标i # 若查完下标也没发现有包含,则返回-1
#一个更好的写法: """ class Solution: def strStr(self, haystack: str, needle: str) -> int: m, n = len(haystack), len(needle) for i in range(m - n + 1): # 窗口起始位置 # 截取子串,判断是否与目标子串匹配 if haystack[i:i + n] == needle: return i return -1 """ # 这个写法是直接截取子串来来判断是否与目标子串匹配的 # 巧妙的点在于: 如果m-n+1<=0则直接不发生循环,直接返回-1;如果能发生循环,m-n+1本身已经确定了能够截取n长度的子串
classSolution: defrepeatedSubstringPattern(self, s: str) -> bool: n = len(s) for i inrange(1, n // 2 + 1): if n % i == 0: for j inrange(i, n): if s[j - i] == s[j]: continue else: break else: returnTrue returnFalse # 经典枚举解法 # 首先理解题目,若有重复子串,则下标只需枚举到n // 2 + 1处 # 随后判断此时枚举处长度能被总串长度整除 # 创建一个用于枚举的变量j,查找i到n的下标位置 # 判断下标j - i的位置的字符是否与下标为j的位置的字符相同 # 若相同则继续查询,若不同则直接退出 # 若循环正常结束没有发生退出,则判定为重复子串
解法2-字符串匹配
1 2 3 4 5 6 7
classSolution: defrepeatedSubstringPattern(self, s: str) -> bool: return (s + s).find(s, 1) != len(s) # 认识到s = t + t + ... # 构造s' = s + s = t + t + t + t + ... # 使用find()方法,在index = 1的位置往后找,在某个index位置找到s # 若满足条件,则此index不可能等于len(s)即添加的第二个s的位置