LeetCode_String

发表于 | 分类于
LeetCode String

14

查找字符串数组中的最长公共前缀。 

1
2
3
4
5
6
7
res = ""
for i in zip(*strs):
    if len(set(i)) == 1:
        res += i[0]
    else:
        break
return res

效率不如遍历查找来的高

58

仅包含大小写字母和空格 ‘ ‘ 的字符串 s中最后一个单词的长度

1
2
3
4
return len(s.strip().split(" ")[-1])

print("".split(" ")) # ['']
print(len(""))      # 0

344

反转数组

1
2
3
4
s.reverse() # 内置方法，C实现，快
s[:] = s[::-1] #切片法，略慢于上述

头尾指针 逐一交换，python自生实现，最慢

345

反转字符串中的元音字母

1
2
3
4
5
6
7
8
9
10
11
12
13
def reverseVowels(self, s: str) -> str:
    S = list(s)
    vowel = ["a","e","i","o","u","A","E","I","U","O"]
    vowel = set(vowel)
    p1 ,p2 = 0, len(s) - 1
    while p1 < p2:
        while S[p1] not in vowel and p1 < p2: p1 += 1
        while S[p2] not in vowel and p1 < p2: p2 -= 1
        if p1 < p2:
            S[p1], S[p2] = S[p2], S[p1]
            p1 += 1
            p2 -= 1
    return "".join(S)

49

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dict_type_word = {}
        for word in strs:
            dict_type_word.setdefault(str(sorted(word)), []).append(word) # 精华所在

        list_result = []
        for it in dict_type_word.values():
            list_result.append(it)

        return list_result

179

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

1
2
输入: [3,30,34,5,9]
输出: 9534330

1
2
3
4
5
6
7
8
9
10
class Solution:
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        from functools import cmp_to_key
        temp = list(map(str,nums))
        temp.sort(key = cmp_to_key(lambda x,y:int(x+y)-int(y+x)),reverse = True )
        return ''.join(temp if temp[0]!='0' else '0')

利用cmp_to_key的返回值辅助sort()方法自定义排序规则

6

按照反N型排列字符串，并按行输出形成新的字符串
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：

1
2
3
L   C   I   R
E T O E S I I G
E   D   H   N

1
2
3
4
5
6
7
8
9
10
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2: return s
        res = ["" for _ in range(numRows)]
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1: flag = -flag
            i += flag
        return "".join(res)

res类似节省空间的二维数组，s逐一将字母放置在指定行中。

316

给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = ['0']

        for i, it in enumerate(s):
            if it not in stack:
                while it < stack[-1] and stack[-1] in s[i+1:]:
                    stack.pop()
                stack.append(it)

        return "".join(stack[1:])

贪心+栈

65

验证给定的字符串是否可以解释为十进制数字。

1
2
3
4
5
-53.5e-93
+1.2e+3

空格 符号 数字 点 数字 E 符号 数字 空格
九种状态

正则表达式解法：

1
2
3
4
5
import re
class Solution:
    def isNumber(self, s: str) -> bool:
        pat = re.compile(r'^[\+\-]?(\d+\.\d+|\.\d+|\d+\.|\d+)(e[\+\-]?\d+)?$')
        return True if len(re.findall(pat, s.strip())) else False

自动机解法：
画出状态转换图
确定合法的终止状态
自动机

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
33
34
class Solution:
    def isNumber(self, s: str) -> bool:
        states = [
            {'blank': 0, 'sign': 1, 'digit': 2, 'dot': 3},
            {'digit': 2, 'dot': 3},
            {'digit': 2, 'dot': 4, 'e': 5, 'blank': 8},
            {'digit': 4},
            {'digit': 4, 'e': 5, 'blank': 8},
            {'sign': 6, 'digit': 7},
            {'digit': 7},
            {'digit': 7, 'blank': 8},
            {'blank': 8}
        ]

        current_state = 0

        for it in s:
            if it in " ":
                it = "blank"
            elif it in "-+":
                it = "sign"
            elif it.isdigit():
                it = "digit"
            elif it == '.':
                it = "dot"

            if it not in states[current_state]:
                return False

            current_state = states[current_state][it]

        if current_state not in [2, 4, 7, 8]:
            return False
        return True