LeetCode-字符串

LeetCode3 无重复字符的最长子串

哈希表，双指针

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n==0 : return 0
        hash_table = {}
        l, max_l, hash_table[s[0]] = 1, 1, 0
        for i in range(1,n):
            if s[i] not in hash_table or i - l > hash_table[s[i]]:
                l = l + 1
            else:
                l = i - hash_table[s[i]]
            max_l = l if l>max_l else max_l
            hash_table[s[i]] = i
        return max_l

LeetCode5 最长回文字符串

回文，马拉车算法

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        ss = '#'.join(s)
        ss = '$#' + ss + '#@'
        n = len(ss)
        p = [1]*n
        lc,right = 0,0
        max_center,max_r = 0,0
        for i in range(1,n-1):
            p[i] = min(p[2*lc-i],right-i) if right-i > 0 else 1
            while(ss[i+p[i]] == ss[i-p[i]]):
                p[i] += 1
            if i+p[i] > right:
                lc = i
                right = i+p[i] -1
            if max_r < p[i]:
                max_center = i
                max_r = p[i]
        s = ''
        for i in ss[max_center-max_r+1:max_center+max_r-1]:
            if i != '#':
                s = s + i
        return s

LeetCode10. 正则表达式匹配

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘* ‘ 的正则表达式匹配。

• ‘.’ 匹配任意单个字符。
• ‘* ‘ 匹配零个或多个前面的元素。
  匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
  说明:
• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        # m,n = len(s),len(p)
        s = s+'$'
        p = p+'$'
        i,j = 0,0
        return self.is_match_core(s,p,i,j)
    
    def is_match_core(self,s,p,i,j):
        if p[j] == '$':
            return s[i] == '$'
        if p[j+1] != '*':
            if s[i] == p[j] or (p[j]=='.' and s[i]!='$'):
                return self.is_match_core(s,p,i+1,j+1)
            else:
                return False
        else:
            while p[j] == s[i] or (p[j]=='.' and s[i]!='$'):
                if self.is_match_core(s,p,i,j+2):
                    return True
                i += 1
            return self.is_match_core(s,p,i,j+2)

LeetCode43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

class Solution:
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        m,n = len(num1),len(num2)
        arr = [0]*(m+n)
        # carray = 0
        for i in range(m-1,-1,-1):
            carray = 0
            for j in range(n-1,-1,-1):
                product = int(num1[i])*int(num2[j]) + carray + arr[i+j+1]
                arr[i+j+1] = product%10
                carray = int(product/10)
            arr[i+j] = carray
        i = 0
        while i<m+n-1 and arr[i] == 0:
            i += 1
        arr = list(map(str,arr))
        return ''.join(arr[i:])

LeetCode44 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

• ‘?’ 可以匹配任何单个字符。
• ‘ *’ 可以匹配任意字符串（包括空字符串）。
  说明:
• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

---

1. 若当前比较的两个字符相同，或者p[j]=’?’,两者都往下走
2. 若p[j]==’‘,这时候先保留当前i和j的位置，即为sstar,pstar,同时j往下走一步（先尝试让 匹配空格），若接下来的步骤都能够匹配就继续下去，否则，让i=sstar+1(匹配一个字符，还不行，匹配两个字符，继续下去，直到s扫描完或者第一个字符匹配成功),同时记录下sstar,以防后面即使出现s[i]==p[j]匹配成功，但其实这样有可能后面的字符不满足，多以还需尝试将这个字符也略过的情况。

---

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        m,n = len(s),len(p)
        # ‘#’作为字符串结束的标识
        s,p = s+'#',p+'#'
        i,j = 0,0
        pstar,sstar = -1,-1
        while i<m:
            if s[i]==p[j] or p[j] == "?":
                i += 1
                j += 1
            elif p[j] == '*':
            # 略过多个*连续的情况
                while p[j]=='*':
                    pstar,j = j,j+1
                sstar = i
            elif pstar>-1:
                j = pstar+1
                sstar,i = sstar+1,sstar
            else:
                return False
        while p[j]=='*': j += 1
        # 若能够匹配，两个字符串都应该走到尾了。
        return s[i] == p[j]

LeetCode93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例：
输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]

class Solution:
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        ip,res = '',[]
        self.dfs(s,0,0,ip,res)
        return res
    def dfs(self,s,start,step,ip,res):
        if start == len(s) and step == 4:
            res.append(ip[:-1])
        if len(s) - start  > (4-step)*3:
            return # 剪枝
        if len(s) - start  < 4-step:
            return
        num = 0
        i = start
        while i < len(s) and i<start+3:
            num = num*10 + int(s[i])
            if num <= 255:
                ip += s[i]
                self.dfs(s,i+1,step+1,ip+'.',res)
            i += 1
            if num == 0:
                break