---

4-2 字符串相关题目

---

版权声明：以下题目均来自 LeetCode， 仅仅提供跳转到力扣官网的链接，不在本页面出现题目内容，本文章内容禁止商业用途。

4.2 目录

序号	题目	题解
①	LeetCode 344.反转字符串	4.2.1题解
②	LeetCode 151.反转字符串中的单词	4.2.2题解
③	LeetCode 557.反转字符串中的单词 III	4.2.3题解
④	LeetCode 3.无重复字符的最长子串	4.2.4题解
⑤	LeetCode 49.字母异位词分组	4.2.5题解
②	LeetCode 125.验证回文串	4.2.6题解
③	LeetCode 415.字符串相加	4.2.7题解
④	LeetCode 43.字符串相乘	4.2.8题解

4.2.1 反转字符串

LeetCode 344.反转字符串 | | 返回目录4.2

思路：这道题其实就是很简单的列表逆序的问题。可以用列表切片或者双指针。需要注意的是题目要求【使用 O(1) 的额外空间】

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        '''
        # 1.直接用列表切片法
        # 但是不符合题目要求的O(1)额外空间
        # 因为python的list切片操作会创建一个临时的list
        s[:] = s[::-1]  
        '''
        # 2.用双指针

        L, R = 0, len(s)-1
        while L < R:
            s[L], s[R] = s[R], s[L]
            L += 1
            R -=1

4.2.2 反转字符串中的单词

LeetCode 151.反转字符串中的单词 | | 返回目录4.2

思路：这个题可能用python来说比较容易，因为python的split能够默认处理空格……
s.split()之后直接就是一个单词列表，然后用4.2.1中的逆序就解决了。而且此题还没有要求空间复杂度，可以直接用list切片操作。

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(s.split()[::-1])

        # 或者也可以用 reversed方法使得 列表逆序
        # return ' '.join( reversed(s.split()))

4.2.3 反转字符串中的单词III

LeetCode 557.反转字符串中的单词 III | | 返回目录4.2

示例 1
思路：和4.2.2换汤不换药，只是对单词内部的字母的逆序而已，不对整体逆序。

class Solution:
    def reverseWords(self, s: str) -> str:
        s_list = s.split()
        return ' '.join([ ele[::-1] for ele in s_list])

        # 这种解法确实能跑通所有样例，是因为：
        # 题目最下方的提示中写了：所有单词都用一个空格隔开。
        # 所以在使用 ' '.join时只用到1个空格， 是可以保证正确的
        # 如果题目不给出这个条件，那就不能直接这么写

拓展：如果题目中没有规定单词之间只有一个空格

class Solution:
    def reverseWords(self, s: str) -> str:
        s_list = list(s)

        # 定义一个逆序的函数
        def reverse_list(a, L, R):
            while L < R:
                a[L], a[R] = a[R], a[L]
                L += 1
                R -=1
        
        # 使用快慢指针
        p1, p2 = 0, 0
        N = len(s_list)
        while p2<N:
            if p2== N-1 or (s_list[p2] != ' ' and s_list[p2+1] == ' '):
                reverse_list(s_list, p1, p2)
            
            if s_list[p2] == ' ' and s_list[p2+1] != ' ':
                p1 = p2+1
            
            p2 += 1

        return ''.join(s_list)

4.2.4 无重复字符的最长子串

LeetCode 3.无重复字符的最长子串 | | 返回目录4.2

思路：这个题的思路和 2-3 数组数组双指针 的 2.3.2.8 只能说一模一样。只不过一个是求连续重复1区间的长度，一个是求不出现重复的区间长度。
：：：
那么核心就是，判断重复与否的条件是什么？
不重复的条件有两个：
1.字符未出现过； 或者
2.字符出现过，但是不在当前判断的区域内，即字符的索引在L边界左侧
：：：
所以对应的重复条件是：
字符出现过，且位于当前判断的区间内，即字符的索引在L右侧

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        N = len(s)
        if N == 0 or N == 1:
            return N 
        L, R = -1, 0
        h = {}
        # 慢指针L表示无重复区域的 左侧外边界
        # 快指针R用来判断当前位置的值是否已经在哈希表中出现
        gap = 0
        
        # 有两种写法
        # 写法1：在未遇到重复字符之前，一直更新区间长度
        # 遇到重复值时，不更新区间长度，而是更新L边界
        for R in range(N):
            # 如果s[R]未出现过, 或者索引位于L左侧, 即当前考察区域更左
            # 说明当前连续未重复区域仍未中断, 可以更新一下gap
            if s[R] not in h or h[s[R]] <= L:
                gap = max(gap, R-L)
            else:
            # L 指向重复元素已经记录的索引位置
            # 相当于将该元素排除出去，新区间从该元素右侧开始考察
                L = h[s[R]]
            h[s[R]] = R
        return gap

        '''
        # 写法2: 在遇到重复元素的时候，才计算一次区间长度
        for R in range(N):
            if s[R] in h and h[s[R]] > L:
            # 出现重复字符时，才计算区间长度，要注意当前位置不算在区间内
                gap = max(gap, R-L -1)
                L = h[s[R]]
            h[s[R]] = R
        # 这里要注意需要补充计算一下最后一段区间的长度
        # 因为R取不到N，否则会漏算最后一段符合条件的区间
        # 比如：若最后一段区间直到N-1都没有出现重复字符，是该计算长度的
        # 但是由于计算的条件是出现重复字符才计算，所以上面并没有机会去计算
        return max(gap, N-L-1)
        '''

4.2.5 字母异位词分组

LeetCode 49.字母异位词分组 | | 返回目录4.2

思路：该题的核心点在于如何判断字母异位词，其实很简单。只需要把单词排序之后，看看它们是否相等。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        h = {}
        for word in strs:
            # 将单词排序，然后来判断其是否出现过
            key = ''.join(sorted(word))
            if key not in h:
                h[key] = [word]
            else:
                h[key] += [word]
        # 直接返回字典的值列表
        return list(h.values())

4.2.6 验证回文串

LeetCode 125.验证回文串 | | 返回目录4.2

思路：这个题也是采用双指针的思路。只不过需要注意，字符串中可能出现不是数字或者字母的字符，所以需要多一个判断条件。

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 先将所有字母转换为小写
        s = s.lower()
        L, R = 0, len(s)-1
        while L < R:
            # while L < R and not (s[L].isalpha() or s[L].isdigit()):
            while L < R and not s[L].isalnum():
                L += 1
            # while L < R and not (s[R].isalpha() or s[R].isdigit()):
            while L < R and not s[R].isalnum():
                R -= 1
            if L < R:
                if s[L] == s[R]:
                    L += 1
                    R -= 1
                else:
                    return False
        return True

4.2.7 字符串相加

LeetCode 415.字符串相加 | | 返回目录4.2

思路：由于题目中明确表示不能够直接将两个输入字符串转换成数字进行计算，所以就需要将其一位一位的拆分之后计算。
此题考察的点就是希望手动模拟按位相加。

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        if num1 == "0" :
            return num2
        elif num2 == "0":
            return num1
        
        else:
            
            m, n = len(num1), len(num2)
            s = ''
            plus = 0 # plus是代表的进位的数字
            k = 1 
            # 因为加法是从个位开始，所以往左遍历字符串
            while plus > 0 or k <= max(m, n):
                a = int(num1[m-k]) if k<=m else 0
                b = int(num2[n-k]) if k<=n else 0
                # digit 表示在当前位置应该出现的数字
                digit = (plus + a + b ) % 10 
                # 新来的字符要加在左侧
                s = str(digit)+s
                # 计算进位数字
                plus = (plus + a+b - digit) // 10
                k+=1
                '''需要注意的是，在计算的时候不要漏加了plus'''
            return s

4.2.8 字符串相乘

LeetCode 43.字符串相乘 | | 返回目录4.2

思路：由于上一题做过字符串相加，我们可以套用其思想，让num2的每一位同num1相乘，然后再加起来即可。

class Solution:
    def multiply(self, num1: str, num2: str) -> str:

        def add_num_list(num_list):
            # 
            # 对2个数字字符串相加的code稍加修改
            # 即可得到对 N 个数字字符串相加的code
            # 当然也可以不做修改，使用2数相加，只需要对每一次做乘法得到的结果，及时应用两数相加即可
            # 
            num_cnt = len(num_list)
            len_num = [len(num) for num in num_list]
            k = 1
            plus = 0
            s = ''
            while plus > 0 or k <= max(len_num):
                a = 0
                for i in range(num_cnt):
                    N_i = len_num[i]
                    '''要点1.是对第i个数字的倒数第k位取值'''
                    a += int(num_list[i][N_i-k]) if k<= N_i else 0
                    # print(k,a)
                '''要点2.这下面的几行要写在for循环之外
                因为for循环结束后，对应位置的数字才相加完毕'''
                digit = (a+plus) % 10
                # print(digit)
                s = str(digit) + s 
                plus = (a+plus-digit) // 10
                k += 1
            return s 

        if num1 == "0" or num2 == "0":
            return "0"
        else:
            num_list = []
            m, n = len(num1), len(num2)
            for j in range(1,n+1):
                # 对num2从个位开始取数
                '''要点3.当j是来自十位、百位、千位...时，屁股后要接上相应个数的0'''
                res = "0"*(j-1)
                b = int(num2[n-j])
                plus = 0
                for i in range(1,m+1):
                    a = int(num1[m-i])
                    digit = (plus + a*b) % 10
                    res = str(digit) + res
                    plus = (plus + a*b -digit) // 10
                '''要点4.for循环玩之后，plus不用留到下一轮，因为该阶段的相加已经结束了
                直接加到数前面去即可'''
                if plus > 0:
                    res = str(plus) + res
                num_list.append(res)
            print(num_list)
            return add_N_num(num_list)
        ##############################################################################
        # 每一次只对两个数字字符串相加，时间上稍微慢一点