字符串笔试

发表于

###回文字符串

从中间去循环向周围扩散，有两种情况，奇数和偶数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) <= 0:
            return 0
        mlength = 0
        slen = ''
        for i in range(0,len(s)):
            l = r = i
            temp = self.check(s,l,r)
            if len(temp) > len(slen):
                slen = temp

            l = i
            r = i + 1
            n = 0
            temp = self.check(s,l,r)
            if len(temp) > len(slen):
                slen = temp


        return slen

    def check(self,s,l,r):
        while(l>=0 and r < len(s) and s[l] == s[r]):
            l-=1
            r+=1
        return s[l+1:r]

###字符串正则匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def isMatch(self, text, pattern):
        memo = {}
        def dp(i, j):
            if (i, j) not in memo:
                if j == len(pattern):
                    ans = i == len(text)
                else:
                    first_match = i < len(text) and pattern[j] in {text[i], '.'}
                    if j+1 < len(pattern) and pattern[j+1] == '*':
                        ans = dp(i, j+2) or first_match and dp(i+1, j)
                    else:
                        ans = first_match and dp(i+1, j+1)

                memo[i, j] = ans
            return memo[i, j]

        return dp(0, 0)

###手机键盘数字转换字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
kvmaps = {'1': '*',
          '2': 'abc',
          '3': 'def',
          '4': 'ghi',
          '5': 'jkl',
          '6': 'mno',
          '7': 'pqrs',
          '8': 'tuv',
          '9': 'wxyz',
          '0': ' '
          }
class Solution(object):
    
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "":
            return []
        combinations = []
        if len(digits) == 1:
            for x in kvmaps[digits[0]]:
                combinations.append(x)
        else:
            for c in self.letterCombinations(digits[1:]):
                for x in kvmaps[digits[0]]:
                    combinations.append(x + c)
        return combinations

###数字转换成IP地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution(object):
    def helper(self, s, dotnum, ret, rets):
        if dotnum > 4 or (len(s) / 3 > 4-dotnum):
            return
        
        if len(s) == 0:
            if dotnum == 4:
                rets.append(ret)
            return

        for i in range(1, 4):
            tmp = s[:i]
            if (dotnum == 3 and i > len(s)) or (i > 1 and s[0] == '0') or (int(tmp) > 255):
                continue
                #如果超长了，如果包含0，如果数值大于255则跳过
            self.helper(s[i:], dotnum+1, ret+'.'+tmp if len(ret) > 0 else tmp, rets)
                
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        rets = []
        self.helper(s, 0, '', rets)
        return rets

###反转句子，词不反转

I am student->student am I

1
2
3
4
5
6
7
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        return " ".join(s.split()[::-1])

###最长公共子串

两个字符串的最长公共子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def minDistance(self, w1, w2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        if not w1: return len(w2)
        if not w2: return len(w1)
        m,n = len(w1), len(w2)
        dp = [[1]*n for _ in range(m)]
        for i in range(m):
            if w1[i] != w2[0]: dp[i][0] = 0
            else: break
        for j in range(n):
            if w1[0] != w2[j]: dp[0][j] = 0
            else: break

        for i in range(1,m):
            for j in range(1,n):
                if w1[i] == w2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        l = dp[-1][-1]
        return m - l + n - l