合并字符串、找不同、找模式字符串

发表于 分类于 ， 本文字数： 4k 阅读时长 ≈ 4 分钟

摘要：刷题日记1：记住一些常用的内置函数方法，这些能帮助简化代码，有时能带来新思路。

合并字符串

题目

给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串 。

示例 1：

输入：word1 = “abc”, word2 = “pqr”
输出：”apbqcr”

示例 2：

输入：word1 = “ab”, word2 = “pqrs”
输出：”apbqrs”

示例 3：

输入：word1 = “abcd”, word2 = “pq”
输出：”apbqcd”

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 先用 zip() 处理部分字符串，然后处理较长字符串的未处理部分，简单来说还是暴力循环
class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        ans = []
        l1, l2 = len(word1), len(word2)
        for w1, w2 in zip(word1, word2):
            ans.append(w1)
            ans.append(w2)
        if l1 > l2:
            for i in range(l2, l1):
                ans.append(word1[i])
        elif l1 < l2:
            for i in range(l1, l2):
                ans.append(word2[i])
        return ''.join(ans)

时间复杂度：$O(n)$，空间复杂度：$O(n)$

评论区解法

  • 这个方法与我的差不多，但是处理的方式明显比我要方便许多——采用字符串相加的方式而非列表转字符串、像遍历列表那样遍历字符串而非使用 for 循环遍历：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        res = ''
        m = len(word1)
        n = len(word2)
        for i, j in zip(word1, word2):
            res += i + j
        if m <= n:
            res += word2[m:]
        else:
            res += word1[n:]
        return res
  • 这个方法借助 itertools 库中的 zip_longest() 函数，其打包方式与 zip() 一样，但是处理方式不一样，当传入的两个迭代对象的长度不一时，前者可以返回到较长对象：
1
2
3
4
5
6
7
8
from itertools import zip_longest
class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        ans = []
        for x, y in zip_longest(word1, word2):
            if x: ans.append(x)
            if y: ans.append(y)
        return ''.join(ans)
  • 第三个方法采用索引的方式遍历字符串，当越界时通过检查来规避越界风险。同样的，也采用了字符串相加的方法：
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        index = 0
        res = ''
        while index < len(word1) or index < len(word2):
            if index < len(word1):
                res += word1[index]
            if index < len(word2):
                res += word2[index]
            index += 1
        return res

找不同

题目

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例 1：

输入：s = “abcd”, t = “abcde”
输出：”e”

示例 2：

输入：s = “”, t = “y”
输出：”y”

解法

用哈希表（字典）统计两个字符串中所有字母出现的次数，不相同则输出该字母：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s_dict = dict[str, int]()
        t_dict = dict[str, int]()
        for i in range(len(t)):
            if i < len(s):
                if not (s[i] in s_dict.keys()):
                    s_dict[s[i]] = 0
                s_dict[s[i]] += 1
            if not (t[i] in t_dict.keys()):
                t_dict[t[i]] = 0
            t_dict[t[i]] += 1
        for key in t_dict.keys():
            if key in s_dict.keys():
                if s_dict[key] != t_dict[key]:
                    return key
            else:
                return key

时间复杂度：$O(n)$，空间复杂度：$O(n)$

评论区解法

  • 将字符转为ASCII码相加，然后二者相减就是多出来的那个字母的ASCII码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        t_sum = 0
        s_sum = 0
        for i in range(len(t)):
            if i < len(s):
                s_sum += ord(s[i])
            t_sum += ord(t[i])
        ans = t_sum - s_sum
        return chr(ans)
# 一样的算法，但是实现方式使用了map函数，很简洁
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return chr(sum(map(ord, t)) - sum(map(ord, s)))
  • 与我的方法类似，也是统计词频，但是这个方法用了字典内置的方法，并且是先累加后累减，找到所剩的那个字母：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        dictTemp = {}
        # 遍历字符串s，用字典统计词频
        for c in s:
            dictTemp[c] = dictTemp.get(c, 0) + 1    # 字典取值操作的时间复杂度是常数阶！
        # 遍历字符串t，字符串t中的字符出现一次，就让字典对应的词频数量减1，最后词频不为0的那个字符就是不同的字符
        for c in t:
            dictTemp[c] = dictTemp.get(c, 0) - 1
        for i in dictTemp:
            if dictTemp[i] != 0:
                return i
  • 剩下这几种方法都借助了字符串内置的 count() 方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 将两个字符串拼接，统计次数，返回奇数次数的字母
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        m = s + t
        for i in m:
            if m.count(i) % 2 == 1:
                return i

# 直接数，出现次数不同就输出
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        for c in t:
            if t.count(c) != s.count(c):
                return c
# 直接数的简洁实现
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return [x for x in t if t.count(x)-s.count(x)==1][0]

找字符串第一个匹配项的下标

题目

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = “sadbutsad”, needle = “sad”
输出：0

示例 2：

输入：haystack = “leetcode”, needle = “leeto”
输出：-1

解法

这个题目其实就是字符串 find() 方法的实现，这个内置方法的时间复杂度是线性阶，空间复杂度是常数阶：

1
2
3
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

我只能想到暴力地遍历求解——先假设不能找到，从下标0开始从目标字符串中抽取相应长的字符串做对比，如果相等则返回，不等则下标右移：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        find = False
        index = 0
        while (index + len(needle)) <= len(haystack):
            if needle == haystack[index: index + len(needle)]:
                find = True
                break
            else:
                index += 1
        if find:
            return index
        else:
            return -1

此方法空间复杂度还是常数阶，但是时间复杂度成了$O(n * m)$

评论区解法

评论区基本没什么新意，但是这里有一个算法：KMP算法是专用于解决这个问题。