day 5: 字符串

朴灿烈づ我的快乐病毒、 2022-12-11 07:47 134阅读 0赞

1. [剑指 Offer 38. 字符串的排列][Offer 38.]

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例：

输入：s = "abc"
    输出：["abc","acb","bac","bca","cab","cba"]

解法1. 递归

class Solution:
        def permutation(self, s: str) -> List[str]: 
            # # 字符串的全排列   
            result = []
            def perm(s_dir, one = ''):
                if s_dir:  
                    buff = []  # 遍历所有字符，不处理 相同字符。 
                    for i, x in enumerate(s_dir):
                        if x not in buff:
                            perm(s_dir[:i] + s_dir[i+1:], one+x)
                            buff.append(x)
                else:  # 找到最后， 相当于 叶子节点
                    # if one not in result:  # 如果在这里判断，会超时
                    result.append(one)
                return 
            perm(s)
            return result

2.  [剑指 Offer 45. 把数组排成最小的数][Offer 45.]

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

**示例 1:**

输入: [10,2]
    输出: "102"

**示例 2:**

输入: [3,30,34,5,9]
    输出:"3033459"提示:
    
    0 < nums.length <= 100
    说明:
    
    输出结果可能非常大，所以你需要返回一个字符串而不是整数
    拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

解法1:  快速排序

class Solution:
        def minNumber(self, nums: List[int]) -> str:
            # 本质上是个 排序 
            # 排序规则： x+y>y+x:  y小
            #          y+x > x +y, x小
            nums_str = [str(item) for item in nums]
            def one_sort(nums, start, end):
                # 一趟排序
                i = start
                j = end
                while i < j:
                    # 从右往左扫描
                    while i<j and nums[i] + nums[j] < nums[j] + nums[i]: 
                        j -= 1
                    if i < j:
                        nums[i], nums[j] = nums[j], nums[i]
                        i = i + 1
                    # 从左往右扫描
                    while i < j and nums[i] + nums[j] < nums[j] + nums[i]: # 
                        i += 1
                    if i < j:
                        nums[i], nums[j] = nums[j], nums[i]
                        j = j - 1
                return i
            # 快速排序算法 
            def quick_sort(nums, start, end):
                if start < end:
                    p = one_sort(nums, start, end)
                    # print(nums)
                    quick_sort(nums, start, p-1)
                    quick_sort(nums, p+1, end)
                    
            quick_sort(nums_str, 0, len(nums_str)-1)
    
            return ''.join(nums_str)

3. [139. 单词拆分][139.]

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。  
你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
    输出: true
    解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
    输出: true
    解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
         注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    输出: false

解法1: 动态规划

class Solution:
        def wordBreak(self, s: str, wordDict: List[str]) -> bool:
            # 从s出发考虑， s中字符 划分后 是否都出现在wordDict
            # 采用 动态规划（不太熟练），遍历字符串;  很巧妙; 从字典开始匹配 递归超时
            dp = [0]*(len(s)+1) 
            dp[0] = 1
            for i in range(1, len(s)+1):
                for j in range(i):
                    if dp[j] == 1 and s[j:i] in wordDict:
                        dp[i] = 1   # 从i 可以开始新的匹配了
                        break
            return dp[i] == 1

4. [140. 单词拆分 II][140. _ II]

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。  
你可以假设字典中没有重复的单词。

示例：

输入:
    s = "pineapplepenapple"
    wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
    输出:
    [
      "pine apple pen apple",
      "pineapple pen apple",
      "pine applepen apple"
    ]
    解释: 注意你可以重复使用字典中的单词。

解法1:  递归 （超时）+ 投机取巧

class Solution:
        def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
            wordDict = sorted(wordDict)
            # any(): 可迭代对象中 若全为Fasle， 则返回False, 否则True;
            # all(): 可迭代对象中 若全为True,  则返回True, 否则Flase
            # 若想 句子中所有单词都在词典中， 句子中的 字母 必须都在 词典中出现的字符中；
            # 若 出现词典中 没出现过字符，则 必定不能组成句子； 
            if any([i not in set("".join(wordDict)) for i in s]):  # 全为False，any 返回false 
                return []   # 通过有点 投机取巧了；
            # 递归 超时 
            result = []
            def digui(s, wordDict, ju=''):
                if not s:
                    result.append(ju.strip())
                for item in wordDict:
                    item_len = len(item)
                    if s[0:0+item_len] == item:  # 匹配成功
                        digui(s[0+item_len:], wordDict, ju + ' ' + item)
                return 
            digui(s, wordDict)
            return result

此题有个测试用例 很恶心：（去掉句子中b 依然超时）

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
    ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

解法2:  从单词的角度去遍历， 也是投机取巧

class Solution:
        def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
            dp = [0]*(len(s)+1) 
            dp[0] = 1
            s_len = len(s)
            if not all([item in set(''.join(wordDict))    for item in s]):
                return []
            # 递归
            result = []
            def digui(s, wordDict, ss=''):  # 
                if not s:
                    result.append(ss.strip())
                s_len = len(s)
                start = 0
                for i in range(s_len + 1):
                    if s[start: start+i] in wordDict:
                        digui(s[start+i:], wordDict, ss + ' ' + s[start: start+i])
                return 
            digui(s, wordDict, '')
            return result

5. [20. 有效的括号][20.]

给定一个只包括 '('，')'，'\{'，'\}'，'\['，'\]' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
注意空字符串可被认为是有效字符串。

**示例 1:**

输入: "()"
    输出: true

**示例 2:**

输入: "()[]{}"
    输出: true

解法1 ：

class Solution:
        def isValid(self, s: str) -> bool:
            if not s:
                return True
            qu_dict = {'(': ')', ')':'(', '{':'}', '}': '{', '[':']', ']':'['}
            # 括号匹配， 先进后出， 后入先出
            result = []
            for item in s:
                if item in [')', '}', ']'] and qu_dict[item] in result:
                    # 可以进去， 是否消除
                    if len(result) > 0 and result[-1] == qu_dict[item]:
                        result.pop()
                    else:
                        result.append(item)
                elif item in ['(', '{', '[']:  # 直接进 不消除
                    result.append(item)
                else: 
                    return False
            if result:
                return False
            return True

解法2: 大神的奇思妙想,  直接替换

class Solution:
        def isValid(self, s: str) -> bool:
            while '()' in s or '[]' in s or '{}' in s:
                s = s.replace('()', '')
                s = s.replace('[]', '')
                s = s.replace('{}', '')
            if s:
                return False
            return True

6. [3. 无重复字符的最长子串][3.]

[剑指 Offer 48. 最长不含重复字符的子字符串][Offer 48.]

给定一个字符串，请你找出其中不含有重复字符的 **最长子串 **的长度。

**示例 1:**

输入: s = "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

**示例 3:**

输入: s = "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
         请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串

解法1: 自创， 思路后续补

class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            max_length = 0
            zichuan = []
            for item in s:
                zichuan.append(item)
                if item in zichuan[:-1]:
                    item_index = zichuan.index(item)
                    zichuan = zichuan[item_index+1:] # 去掉前面重复的
    
                max_length = max(max_length, len(zichuan))
            return max_length

解法2: 官方 滑动窗口

class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            # 官方解法 滑动窗口， 找 从头开始， 以每个字符开始 对应的 最长子串（没有重复字符）， 比较长度 找到最大的；
            
            s_len = len(s)
            nk, max_len = -1, 0  # nk表示滑动窗口右侧，-1表示还没移动
            sets = set() # 哈希表, 判断是否 重复字符
            for i in range(s_len):
                if i != 0:
                    sets.remove(s[i-1])  # 开始指针下移一步
                while nk+1 < s_len and s[nk+1] not in sets:
                    sets.add(s[nk+1])
                    nk = nk + 1
                # 出现重复的值了, 就是 i~nk 没有重复字符的 最长字串
                max_len = max(max_len, nk-i+1) 
            return max_len

7. [394. 字符串解码][394.]

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k\[encoded\_string\]，表示其中方括号内部的 encoded\_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2\[4\] 的输入。

**示例 1：**

输入：s = "3[a]2[bc]"
    输出："aaabcbc"

解法1:

class Solution:
        def decodeString(self, s: str) -> str:
            ### 简单在 所有数字 只表示重复次数k， 数字只表示重复；
            res = []
            for item in s:
                if item == "]": # 遇到"]" 回溯
                    ress = ""
                    while res and res[-1] != '[': # 方括号内部字母
                        ress = res.pop()+ress
                    res.pop() # 输出[
                    # 得到方括号前的数字
                    nums = ""
                    while res and res[-1].isdigit():
                        nums = res.pop()+nums
                    if nums:
                        res.append(int(nums) * ress)
                    else:
                        res.append(ress)
                else:
                    res.append(item)
            # print(res)
            return "".join(res)

[Offer 38.]: https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
[Offer 45.]: https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
[139.]: https://leetcode-cn.com/problems/word-break/
[140. _ II]: https://leetcode-cn.com/problems/word-break-ii/
[20.]: https://leetcode-cn.com/problems/valid-parentheses/
[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[Offer 48.]: https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
[394.]: https://leetcode-cn.com/problems/decode-string/