LeetCode算法题整理（字符串篇）String

Posted on   |   Updated on | In | | Visitors

14. Longest Common Prefix

返回最长公共前缀字符串。原题

1
2
Input: ["flower","flow","flight"]
Output: "fl"
1
2
3
4
5
6
def longest_common_prefix(strs):
    if not strs:
        return ''
    from itertools import takewhile
    max_pre_len = len(list(takewhile(lambda x: len(set(x))==1, zip(*strs))))
    return strs[0][:max_pre_len]

20. Valid Parentheses

判断括号是否成对出现，并且嵌套正确。原题

1
2
3
4
Input: "()[]{}"
Output: true
Input: "{[]}"
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
def is_valid(s):
    pairs = {')': '(', '}': '{', ']': '['}
    stack = []
    for paren in s:
        if paren in pairs.values():
            stack.append(paren)
        elif paren in pairs.keys():
            if stack == [] or stack.pop() != pairs[paren]:
                return False
        else:
            return False

    return stack == []

921. Minimum Add to Make Parentheses Valid

给定一个只包含小括号的字符串。返回需要多少个”(“或”)”使其成为完整的括号表达式。原题

1
2
3
4
5
6
7
8
Input: "())"
Output: 1
Input: "()))(("
Output: 4
Input: "()"
Output: 0
Input: "((("
Output: 3

方法一：平衡问题。

1
2
3
4
5
6
7
8
def minAddToMakeValid(self, S: str) -> int:
    ans = bal = 0
    for symbol in S:
        bal += 1 if symbol=='(' else -1
        if bal == -1:
            ans += 1
            bal += 1
    return ans + bal

28. Implement strStr()

实现index。原题

1
2
Input: haystack = "hello", needle = "ll"
Output: 2
1
2
3
4
5
6
7
8
def str_index(haystack, needle):
    h = len(haystack)
    n = len(needle)
    for i in range(h-n+1):
        if haystack[i:i+n] == needle:
            return i
    else:
        return -1

38. Count and Say

原题

1
2
3
4
5
1.     1
2.     11
3.     21
4.     1211
5.     111221
1
2
3
4
5
6
def countAndSay(self, n: int) -> str:
    ans = '1'
    for _ in range(n-1):
        ans = ''.join(str(len(list(c)))+d 
                      for d, c in itertools.groupby(ans))
    return ans

443. String Compression

字符串压缩，实际是要将重复的字符串以个数来表示。要求O(1)空间复杂度，就地修改原数组。原题

思路：看上去和38题差不多，但是有些不同，不同的地方在于如果个数为1，则不显示。个数为两位数，要显示两个元素。

1
2
3
4
5
6
Input = ["a","a","b","b","c","c","c"]
Output = ["a","2","b","2","c","3"]
Input = ["a"]
Output = ["a"]
Input = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output = ["a","b","1","2"]
1
2
3
4
5
6
7
8
9
10
11
12
def compress(self, chars: List[str]) -> int:
    anchor, write = 0, 0   # anchor为每组连续的第一个位置。
    for r, char in enumerate(chars):
        if r == len(chars)-1 or char != chars[r+1]:
            chars[write] = chars[anchor]
            write += 1
            if r > anchor:
                for digit in str(r - anchor + 1):
                    chars[write] = digit
                    write += 1
            anchor = r + 1
    return write

125. Valid Palindrome

验证回文字符串，只判断字母数字，忽略大小写。原题

1
2
Input: "A man, a plan, a canal: Panama"
Output: true

方法一：切片

1
2
3
def is_palindrome(s):
    s_alnum = filter(str.isalnum, s.lower())
    return s_alnum == s_alnum[::-1]

方法二：双指针

1
2
3
4
5
6
7
def is_palindrome(s):
    s_alnum = list(filter(str.isalnum, s.lower()))
    mid = len(s_alnum) // 2
    for i in range(mid):
        if s_alnum[i] != s_alnum[-i-1]:
            return False
    return True

680. Valid Palindrome II

验证是否是回文数，只包含小写字母，但是允许最多去掉一个字母之后是回文数。原题

1
2
3
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

方法一：一开始想的方法。切片由于可能i=0，所以必须反序切片再倒置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def validPalindrome(self, s):
    i, res = self.is_palindrome(s)
    if res:
        return True
    else:
        _, s1 = self.is_palindrome(s[:i]+s[i+1:]) 
        left = slice(0, -i-1)
        right = slice(-1, -i-1, -1)
        _, s2 = self.is_palindrome(s[left]+s[right][::-1])
        return s1 or s2
        
def is_palindrome(self, s):
    mid = len(s) // 2
    # print(s)
    for i in range(mid):
        if s[i] != s[-i-1]:
            # print('{} [{}] != [{}]'.format(s, s[i], s[-i-1]))
            return i, False
    return None, True
方法二：双指针方法。 
1
2
3
4
5
6
7
8
def validPalindrome(self, s):
    l, r = 0, len(s)-1
    while l < r:
        if s[l] != s[r]:
            one, two = s[l:r], s[l+1:r+1]
            return one==one[::-1] or two==two[::-1]
        l, r = l+1, r-1
    return True

方法三：贪心解法，留坑。

151. Reverse Words in a String

倒置一句话中的单词。原题

1
2
Input: "the sky is blue",
Output: "blue is sky the".
1
2
def reverse_words(s):
    return ' '.join(s.split()[::-1])

344. Reverse String

倒置字符串。原题

1
2
Input: "A man, a plan, a canal: Panama"
Output: "amanaP :lanac a ,nalp a ,nam A"
1
2
3
4
5
6
def reverse_str(s):
    n = len(s)
    res = list(s)
    for i in range(n//2):
        res[i], res[-i-1] = res[-i-1], res[i]
    return ''.join(res)

242. Valid Anagram

验证回文构词法，即两个字符串由同样个数的字符组成。原题

1
2
Input: s = "anagram", t = "nagaram"
Output: true

方法一： sort

1
2
def is_anagram(s, t):
    return sorted(s) == sorted(t)

方法二：Counter

1
2
3
4
5
def is_anagram(s, t):
    from collections import Counter
    c1 = Counter(s)
    c2 = Counter(t)
    return c1 == c2

438. Find All Anagrams in a String

找出字符串中所有的回文构词。原题

方法一：有个小地方注意就是，如果计数为0要删除，否则等式将不成立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findAnagrams(self, s, p):
    from collections import Counter
    ns, np = len(s), len(p)
    cur_c = Counter(s[:np-1])
    c_p = Counter(p)
    res = []
    for i in range(np-1, ns):
        cur_c[s[i]] += 1
        if cur_c == c_p:
            res.append(i-np+1)
        cur_c[s[i-np+1]] -= 1
        if cur_c[s[i-np+1]] == 0:
            del cur_c[s[i-np+1]]
    return res

3. Longest Substring Without Repeating Characters

最长不含重复字符的子字符串。原题

方法一：暴力法，果然超时了。

1
2
3
4
5
6
7
def lengthOfLongestSubstring(self, s):
    max_len, n = 0, len(s)
    for i in range(n):
        for j in range(i+1, n+1):
            if len(s[i:j]) == len(set(s[i:j])):
                max_len = max(max_len, len(s[i:j]))
    return max_len
方法二：找到重复值时，更新start的值，为什么使用max，因为start有可能大于dic[s[end]]+1，比如当s='abba'，end走到最后的时候，上一次start因为b做了更新变为了2。 
1
2
3
4
5
6
7
8
9
10
def lengthOfLongestSubstring(self, s):
    res, start = 0, 0
    dic = {}
    for end in range(len(s)):
        if s[end] in dic:
            start = max(start, dic[s[end]]+1)
            # start = dic[s[end]] + 1
        dic[s[end]] = end
        res = max(res, end-start+1)
    return res

也可以把max判断放到条件里。

1
2
3
4
5
6
7
8
9
10
def lengthOfLongestSubstring(self, s):
    res, start = 0, 0
    dic = {}
    for end in range(len(s)):
        if s[end] in dic and start <= dic[s[end]]:
            start = dic[s[end]] + 1
        else:
            res = max(res, end-start+1)
        dic[s[end]] = end
    return res

387. First Unique Character in a String

返回第一个不重复的字符。原题

1
2
3
4
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.

Time-O(N), Space-O(N)。暂时没发现更快的算法了。

1
2
3
4
5
6
7
def firstUniqChar(self, s):
    from collections import Counter
    c = Counter(s)
    for i, ch in enumerate(s):
        if c[ch] == 1:
            return i
    return -1

58. Length of Last Word

输入一个字符串，通过空格分割，然后返回最后一个单词的长度，空串不算。原题

1
2
3
4
5
6
s = "Hello World"
return 5
s = "a "
return 1
s = "    "
return 0

方法一：直观的方法。

1
2
3
4
5
6
def lengthOfLastWord(self, s):
    ss = s.split(' ')
    for ch in ss[::-1]:
        if ch:
            return len(ch)
    return 0

方法二：使用列表生成式，理论上时间复杂度比上述方法稍微高一点，不过实际时间差不多，估计是list comprehension做了优化。

1
2
3
def lengthOfLastWord(self, s):
    ss =[x for x in s.split(' ') if x]
    return len(ss[-1]) if ss else 0

205. Isomorphic Strings

判断两个字符串是否具有一样的形式。s和t长度一样。原题

1
2
3
4
5
6
7
8
Input: s = "egg", t = "add"
Output: true

Input: s = "foo", t = "bar"
Output: false

Input: s = "paper", t = "title"
Output: true

方法一：使用dict保存每个字母的位置。这里使用了OrderedDict保存了values的顺序，也可以使用sorted对values排序。最后说明一下在Python3中需要使用list格式化一下，因为values()返回一个dict_values对象，而这个对象如果直接使用==判断，会返回False，即使有相同的值，这里还不清楚内部的__eq__方法是如何实现的。而在Python2中可以直接比较。

1
2
3
4
5
6
7
8
def isIsomorphic(self, s, t):
    from collections import OrderedDict
    d1, d2 = OrderedDict(), OrderedDict()
    for i, val in enumerate(s):
        d1[val] = d1.get(val, []) + [i]
    for i, val in enumerate(t):
        d2[val] = d2.get(val, []) + [i]
    return list(d1.values()) == list(d2.values())

方法二：使用zip并行输出。

1
2
>>> list(zip('paper', 'title'))
[('p', 't'), ('a', 'i'), ('p', 't'), ('e', 'l'), ('r', 'e')]
1
2
def isIsomorphic(self, s, t):
    return len(set(zip(s, t))) == len(set(s)) == len(set(t))

方法三：两个字符串每个位置的字符，第一次出现的index是否相同。

1
2
3
def isIsomorphic(self, s, t): 
    # return [s.find(i) for i in s] == [t.find(j) for j in t]
    return list(map(s.find, s)) == list(map(t.find, t))

方法四：setdeault妙用。Lee215。

1
2
3
4
5
6
7
def isIsomorphic(self, s: str, t: str) -> bool:
    
    def f(w):
        m = {}
        return [m.setdefault(c, len(m)) for c in w]
    
    return f(s) == f(t)

290. Word Pattern

匹配字符串和空格分隔的字符串是否具有相同形式，此题和上一题相似，只不过将其中一个换成了数组。另一个区别是长度不一定相等。原题

1
2
Input: pattern = "abba", str = "dog cat cat dog"
Output: true
1
2
3
4
def wordPattern(self, pattern, str):
    s = pattern
    t = str.split()
    return list(map(s.find, s)) == list(map(t.index, t))
1
2
3
4
5
def wordPattern(self, pattern, str):
    s = pattern
    t = str.split()
    return len(set(zip(s, t))) == len(set(s)) == len(set(t)) \
           and len(s) == len(t)
1
2
3
4
5
6
7
def wordPattern(self, pattern: str, str: str) -> bool:
    
    def f(w):
        m = {}
        return [m.setdefault(c, len(m)) for c in w]
    
    return f(pattern) == f(str.split())

890. Find and Replace Pattern

找到和pattern一样模式的字符串。和290，205一样。原题

1
2
3
4
5
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
since a and b map to the same letter.

方法一：我使用zip和set来判断的。

1
2
3
4
5
6
7
def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
    
    def same(a, b):
        return len(set(a)) == len(set(b)) == len(set(zip(a, b)))
    
    return [word for word, p in zip(words, itertools.repeat(pattern)) 
            if same(word, p)]
方法二：Lee215的方法。setdefault的妙用。 
1
2
3
4
5
6
7
def findAndReplacePattern(self, words: List[str], p: str) -> List[str]:
    
    def F(w):
        m = {}
        return [m.setdefault(c, len(m)) for c in w]
    
    return [w for w in words if F(w) == F(p)]

917. Reverse Only Letters

倒置一个字符串的字母。原题

1
2
3
4
5
Input: "ab-cd"
Output: "dc-ba"

Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

注意：不能使用l <= r作为条件，因为会打乱正确结果的排序。输出"dcb-a"。

1
2
3
4
5
6
7
8
9
10
11
12
def reverseOnlyLetters(self, S):
    l, r = 0, len(S)-1
    res = list(S)
    while l < r:
        while l<r and not res[l].isalpha():
            l += 1
        while l<r and not res[r].isalpha():
            r -= 1
        res[l], res[r] = res[r], res[l]
        l += 1
        r -= 1
    return ''.join(res)

345.Reverse Vowels of a String

倒置一个字符串中的元音字母。原题

1
2
3
4
Example 2:

Input: "leetcode"
Output: "leotcede"

方法一：和917题一样，换汤不换药。只需定义一个vowels={'a', 'e', 'i', 'o', 'u'}然后条件改成while l<r and res[l].lower() not in vowels:，提交了一下beat有68%左右，应该还有更效率的方法。

方法二：改了一下，不再使用lower方法了，把大写字母加上，beat变为99.88%。

1
2
3
4
5
6
7
8
9
10
11
12
13
def reverseVowels(self, s):
    l, r = 0, len(s)-1
    vowels = set(list('aeiouAEIOU'))
    res = list(s)
    while l < r:
        while l<r and res[l] not in vowels:
            l += 1
        while l<r and res[r] not in vowels:
            r -= 1
        res[l], res[r] = res[r], res[l]
        l += 1
        r -= 1
    return ''.join(res)

方法三：正则

1
2
3
4
def reverseVowels(self, s):
    vowels = re.findall('(?i)[aeiou]', s)   # (?i)表示忽略大小写
    # repl参数每次返回一个值，用来替换s匹配pattern的字符。
    return re.sub('(?i)[aeiou]', lambda m: vowels.pop(), s)

383. Ransom Note

判断是否magazine可以构成ransomNote。原题

1
2
3
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

方法一：使用count。

1
2
3
4
5
def canConstruct(self, ransomNote, magazine):
    for item in set(ransomNote):
        if magazine.count(item) < ransomNote.count(item):
            return False
    return True
方法二：one-liner. 
1
2
3
def canConstruct(self, ransomNote, magazine):
    return all(ransomNote.count(char) <= magazine.count(char) 
               for char in set(ransomNote))
方法三：Counter。时间复杂度比二稍高。 
1
2
3
def canConstruct(self, ransomNote, magazine):
    from collections import Counter
    return not Counter(ransomNote) - Counter(magazine)

925. Long Pressed Name

说有这么一个破键盘，老是连键，有时候打一个字母c，出来好几个。给定一个目标字符串和打出来的字符串，判断是否是这个破键盘输出的。原题

1
2
3
4
5
6
7
Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it wasn't in the typed output.

思路：一开始还想用Counter，后来发现不对，因为它将所有的一样的字符聚合到了一起。所以此题可以使用groupby

1
2
3
4
5
6
7
8
9
10
11
def isLongPressedName(self, name, typed):
    from itertools import groupby
    name_groups = [(ch, len(list(g))) for ch, g in groupby(name)]
    typed_groups = [(ch, len(list(g))) for ch, g in groupby(typed)]
    if len(typed_groups) < len(name_groups):
        return False
    for i in range(len(name_groups)):
        if typed_groups[i][0] != name_groups[i][0] or \
            typed_groups[i][1] < name_groups[i][1]:
            return False
    return True
方法二：简单的写法。 
1
2
3
4
5
6
7
8
def isLongPressedName(self, name: str, typed: str) -> bool:
    ngroups = itertools.groupby(name)
    tgroups = itertools.groupby(typed)
    for (nl, nc), (tl, tc) in itertools.zip_longest(
            ngroups, tgroups, fillvalue=('~', [])):
        if nl != tl or len(list(nc)) >len(list(tc)):
            return False
    return True

929. Unique Email Addresses

统计不同的email地址。原题

1
2
3
4
5
6
7
8
9
def numUniqueEmails(self, emails):
    res = set()
    for email in emails:
        local, domain = email.split('@')
        if '+' in local:
            local = local[:local.index('+')]
        local = local.replace('.', '')
        res.add((local, domain))
    return len(res)

409. Longest Palindrome

给你一堆字符串，返回用它组成的最长的回文串的长度，可以不使用所有的字符。原题

方法一：每对一样的数字可以放在两边来组成回文。

1
2
3
4
5
6
7
def longestPalindrome(self, s):
    from collections import Counter
    c = Counter(s)
    res = 0
    for count in c.values():
        res += count // 2
    return res*2 + (len(s) > res*2)
方法二：从奇数的角度考虑。 
1
2
3
4
def longestPalindrome(self, s):
    from collections import Counter
    odds = sum(v & 1 for v in Counter(s).values())
    return len(s) - odds + bool(odds)  # 如果有奇数，总能将其放到中间

434. Number of Segments in a String

统计字符串中有多少个以空格分割的字符串。原题

方法一：Time-O(n), Space-O(1) 
1
2
3
4
5
6
def countSegments(self, s):
    segment_count = 0
    for i in range(len(s)):
        if (i == 0 or s[i-1] == ' ') and s[i] != ' ':
            segment_count += 1
    return segment_count

方法二：

1
2
def countSegments(self, s):
    return len(s.split())

500. Keyboard Row

输入一个字符串数组，返回字符在键盘同一行的字符串。原题

1
2
Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findWords(self, words):
        self.first = {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'}
        self.second = {'A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L'}        
        self.third = {'Z', 'X', 'C', 'V', 'B', 'N', 'M'}
        return list(filter(self.same_line, words))
        
    def same_line(self, word):
        return set(word.upper()) <= set(self.first) or \
               set(word.upper()) <= set(self.second) or \
               set(word.upper()) <= set(self.third)

520. Detect Capital

判断一个字符串的大写是否使用正确。要么全大写，要么全小写，或者首字母大写。原题

1
2
Input: "USA"
Output: True

方法一：太简单了，一下子就写出来了，看评论居然好多人不知道istitle。

1
2
def detectCapitalUse(self, word):
    return word.islower() or word.isupper() or word.istitle()

541. Reverse String II

按照2k的长度划分一个字符串，把其中每段前k个字符倒置。原题

1
2
Input: s = "abcdefg", k = 2
Output: "bacdfeg"

方法一：比较简单的一题，使用Python的切片。

1
2
3
4
5
6
7
8
def reverseStr(self, s, k):
    letters = list(s)
    n = len(letters)
    # for i in range(n//(2*k)+1):
        # letters[2*k*i:k+2*k*i] = reversed(letters[2*k*i:k+2*k*i])
    for i in range(0, n, 2*k):
        letters[i:k+i] = reversed(letters[i:k+i])
    return ''.join(letters)

551. Student Attendance Record I

判断一个学生是否有奖励，缺席次数小于等于一天，没有三次连续的迟到。原题

1
2
Input: "PPALLP"
Output: True
1
2
def checkRecord(self, s):
    return s.count('A')<= 1 and 'LLL' not in s

557. Reverse Words in a String III

倒置一句话中的每个单词。所有单词均已一个空格分隔。原题

1
2
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
1
2
def reverseWords(self, s):
    return ' '.join([word[::-1] for word in s.split()])

657. Robot Return to Origin

机器人是否能回到原点。’UDLR’分别表示上下左右，每次移动的距离一样。原题

1
2
3
Input: "UD"
Output: true 
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.

方法一：就是看上下和左右的次数是否一样。此题过于简单。

1
2
3
def judgeCircle(self, moves):
    return moves.count('L') == moves.count('R') and \
           moves.count('U') == moves.count('D')
1
2
3
4
def judgeCircle(self, moves):
    from collections import Counter
    c = Counter(moves)
    return c['U'] == c['D'] and c['L'] == c['R']

696. Count Binary Substrings

二进制字符串计数，有多少个连续的子字符串，由相同的0和1组成，如’10’，’1100’。原题

1
2
3
4
5
6
7
Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.
方法一：正则要比groupby快. 
1
2
3
4
5
def countBinarySubstrings(self, s):
    from itertools import groupby
    # groups = [len(list(v)) for _, v in groupby(s)]
    groups = list(map(len, re.findall('0+|1+', s)))
    return sum(min(a, b) for a, b in zip(groups, groups[1:]))

方法二：变量，常数空间复杂度。

1
2
3
4
5
6
7
8
9
def countBinarySubstrings(self, s):
    res, prev, cur = 0, 0, 1
    for i in range(1, len(s)):
        if s[i] != s[i-1]:
            res += min(prev, cur)
            prev, cur = cur, 1
        else:
            cur += 1
    return res + min(prev, cur)

709. To Lower Case

实现字符串的lower方法。原题

1
2
Input: "Hello"
Output: "hello"
1
2
3
def toLowerCase(self, str):
    return ''.join(chr(ord(c)+32) if 65<=ord(c)<=90 else c
                   for c in str)

771. Jewels and Stones

判断S里有多少个在J里，J为不重复元素。原题

1
2
Input: J = "aA", S = "aAAbbbb"
Output: 3

方法一：使用set.

1
2
3
def numJewelsInStones(self, J: 'str', S: 'str') -> 'int':
    jewels = set(J)
    return sum(s in jewels for s in S)

方法二：count. count的值只会是0和1，因为J没有重复元素。由于这个特性，所以反过来也是一样。

1
2
3
def numJewelsInStones(self, J: 'str', S: 'str') -> 'int':
    # return sum(map(J.count, S))
	return sum(map(S.count, J))

784. Letter Case Permutation

字母组合，给定一个字符串，其中的字母可大写可小写，返回所有可能的字符串。原题

1
2
3
4
5
6
7
8
9
Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]

方法一：提取字母，然后format。

1
2
3
4
5
6
7
def letterCasePermutation(self, S: 'str') -> 'List[str]':
    letters = ''.join(x for x in S if x.isalpha())
    s = re.sub(r'[A-Za-z]', '{}', S)
    ans = ['']
    for l in letters:
        ans = [pre+x for pre in ans for x in (l.lower(), l.upper())]
    return [s.format(*f) for f in ans]
方法二：一开始被题目误导了，以为是排列，后来想到了笛卡尔乘积，但是没想到可以这样写。 
1
2
3
4
def letterCasePermutation(self, S: 'str') -> 'List[str]':
    L = ((s.lower(), s.upper()) if s.isalpha() else s for s in S)
    # [('a', 'A'), '1', ('b', 'B'), '2']
    return [''.join(c) for c in itertools.product(*L)]

788. Rotated Digits

可旋转的数字，说把一个数的所有数字旋转180度，是一个正确的数字。并且和原来不同。给定一个N，返回1~N所有这样的数的个数。原题

1
2
3
4
5
6
Example:
Input: 10
Output: 4
Explanation: 
There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.
1
2
3
4
5
def rotatedDigits(self, N: 'int') -> 'int':
    changed = {'2', '5', '6', '9'}
    valid = changed | {'0', '1', '8'}
    return sum(bool(set(str(i))<=valid and set(str(i))&changed)
               for i in range(1, N+1))

796. Rotate String

判断一个字符串A是否可以旋转成B。原题

1
2
3
4
5
6
7
Example 1:
Input: A = 'abcde', B = 'cdeab'
Output: true

Example 2:
Input: A = 'abcde', B = 'abced'
Output: false

方法一：Brute Force. Time: O(N²), Space: O(N²).

1
2
3
4
5
def rotateString(self, A: 'str', B: 'str') -> 'bool':
    for k in range(len(A)):
        if A[-k:] + A[:-k] == B:
            return True
    return False if A else A==B
方法二：Time O(N²). Space O(N). 
1
2
def rotateString(self, A: 'str', B: 'str') -> 'bool':
    return len(A)==len(B) and B in A*2

方法三：KMP算法。留坑。

方法四：Rolling Hash算法。留坑。

804. Unique Morse Code Words

不重复的莫斯密码，给定一句话，求不重复的单词的莫斯密码个数。原题

1
2
3
4
5
6
7
8
9
10
11
Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation: 
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

There are 2 different transformations, "--...-." and "--...--.".
1
2
3
4
5
6
7
def uniqueMorseRepresentations(self, words: 'List[str]') -> 'int':
    codes = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
    # morse = dict(zip(string.ascii_lowercase, codes))
    # seen = {''.join(morse[c] for c in word) for word in words}
    seen = {''.join(codes[ord(c)-ord('a')] for c in word) 
           for word in words}
    return len(seen)

806. Number of Lines To Write String

单词换行，已知每个字母的宽度，每100一换行，写不下一个字母时，换行，最一个字符串需要多少行和末尾行的宽度。原题

1
2
3
4
5
6
7
8
Example :
Input: 
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
Output: [3, 60]
Explanation: 
All letters have the same length of 10. To write all 26 letters,
we need two full lines and one line with 60 units.
1
2
3
4
5
6
7
8
9
def numberOfLines(self, widths: 'List[int]', S: 'str') -> 'List[int]':
    width = dict(zip(string.ascii_letters, widths))
    lines, line = 1, 0
    for s in S:
        if line + width[s] > 100:
            lines += 1
            line = 0
        line += width[s]
    return lines, line

819. Most Common Word

最常见的单词，从输入的段落中找到出现频率最高并且不在banned列表中的单词。原题

1
2
3
4
5
6
7
8
9
10
Input: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

方法一：一开始写的方法。

1
2
3
4
5
6
7
8
def mostCommonWord(self, paragraph: 'str', banned: 'List[str]') -> 'str':
    words = re.split(r'[!?\',;. ]', paragraph.lower())
    c = collections.Counter(words)
    banned = set(banned)
    for word, count in c.most_common():
        if word and word not in banned:
            return word
    return ''
方法二：上述方法的优化。 
1
2
3
4
5
def mostCommonWord(self, paragraph: 'str', banned: 'List[str]') -> 'str':
    words = re.findall(r'\w+', paragraph.lower())
    banset = set(banned)
    return collections.Counter(
        (w for w in words if w not in banset)).most_common(1)[0][0]

821. Shortest Distance to a Character

根据已知字符串S, 求目标字符C和左右index最近的距离。原题

1
2
Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

方法一：前后遍历两次，分别求距离。本想通过一次，结果实现过于繁琐。

1
2
3
4
5
6
7
8
def shortestToChar(self, S: 'str', C: 'str') -> 'List[int]':
    n = len(S)
    ans = [0 if x == C else n for x in S]
    pos = -n
    for i in list(range(n)) + list(range(n)[::-1]):
        if ans[i] == 0: pos = i
        ans[i] = min(ans[i], abs(pos-i))
    return ans

824. Goat Latin

山羊拉丁口音，把一句话中的每个单词根据规则，生成一句新的话。原题

1
2
Input: "The quick brown fox jumped over the lazy dog"
Output: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"
1
2
3
4
5
6
7
8
9
def toGoatLatin(self, S: 'str') -> 'str':
    vowels = set('aeiouAEIOU')
    words = []
    for i, word in enumerate(S.split(), start=1):
        if word[0] not in vowels:
            word = word[1:] + word[0]
        word += 'ma'+'a'*i
        words.append(word)
    return ' '.join(words)

844. Backspace String Compare

退格键字符串比较。比较两个带有退格#的字符串，判断最后输出是否一致。原题

1
2
3
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

方法一：首先想到stack.

1
2
3
4
5
6
7
8
9
10
11
12
def backspaceCompare(self, S: 'str', T: 'str') -> 'bool':
    
    def type_text(s):
        stack = []
        for c in s:
            if c != '#':
                stack.append(c)
            elif stack:
                stack.pop()
        return stack
    
    return type_text(S) == type_text(T)
方法二：two pointers. Space Complexity: O(1). 
1
2
3
4
5
6
7
8
9
10
11
12
13
def backspaceCompare(self, S: 'str', T: 'str') -> 'bool':
    
    def type_c(s):
        skip = 0
        for x in reversed(s):
            if x == '#':
                skip += 1
            elif skip:
                skip -= 1
            else:
                yield x
    
    return all(x==y for x, y in itertools.zip_longest(type_c(S), type_c(T)))
方法三：这个方法也很有意思，理论上效率不高，但实际上也并无差别。使用reduce然后切片去掉上次结果的末尾元素。最后一个空串的参数表明了一个初始化参数。如果没有它，#a#c的结果会变成#c。因为第一次循环相当于back('#', 'a')所以第一个#会一直保留。 
1
2
3
4
def backspaceCompare(self, S: 'str', T: 'str') -> 'bool':
    from functools import reduce
    back = lambda res, c: res[:-1] if c == '#' else res + c
    return reduce(back, S, '') == reduce(back, T, '')

查看文档中reduce实现：

1
2
3
4
5
6
7
8
9
def reduce(function, iterable, initializer=None):
    it = iter(iterable)
    if initializer is None:
        value = next(it)
    else:
        value = initializer
    for element in it:
        value = function(value, element)
    return value

859. Buddy Strings

好友字符串。指A通过一次交换两个字符变成B。判断是否是好友字符串。原题

1
2
3
4
Input: A = "ab", B = "ba"
Output: true
Input: A = "ab", B = "ab"
Output: false

方法一：Brute Force. 效率很低。

1
2
3
4
5
6
7
8
9
10
11
12
13
def buddyStrings(self, A: 'str', B: 'str') -> 'bool':
    if len(A) != len(B) or set(A) != set(B):
        return False
    seen = set()
    for i in range(len(A)):
        if A[i] not in seen:
            seen.add(A[i])
        else:
            continue
        for j in range(i+1, len(A)):
            if A[:i] + A[j] + A[i+1:j] + A[i] + A[j+1:] == B:
                return True
    return False
方法二：此题分为两种情况，一种是A==B，此时判断是否有重复元素；另一种找到不相等的对，有且只能有一对。结尾len(pairs)的判断虽然显得有些重复，不过可以在某些情况提前退出提高效率，所以没有写成列表生成式的形式。 
1
2
3
4
5
6
7
8
9
10
11
def buddyStrings(self, A: 'str', B: 'str') -> 'bool':
    if len(A) != len(B): return False
    if A == B:
        return len(A) != len(set(A))
    else:
        pairs = []
        for a, b in zip(A, B):
            if a != b:
                pairs.append((a, b))
            if len(pairs) >= 3: return False
        return len(pairs) == 2 and pairs[0] == pairs[1][::-1]

893. Groups of Special-Equivalent Strings

特殊等价字符串组。这题Contest就没做出来，描述有问题，讨论区一堆diss的评论。总的来说就是把A的字符串分组，能够改变偶数位的字符，或奇数位的字符能使之相等的为一组，求一共有多少个组。原题

1
2
3
4
5
6
7
8
9
10
11
Input: ["a","b","c","a","c","c"]
Output: 3
Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]

Input: ["abcd","cdab","adcb","cbad"]
Output: 1
Explanation: 1 group ["abcd","cdab","adcb","cbad"]

方法一：数组保留索引。

1
2
3
4
5
6
7
8
def numSpecialEquivGroups(self, A: 'List[str]') -> 'int':
    def count(A):
        ans = [0] * 52
        for i, letter in enumerate(A):
            ans[ord(letter) - ord('a') + 26 * (i%2)] += 1
        return tuple(ans)

    return len({count(word) for word in A})
方法二：切片字符串排序。 
1
2
3
def numSpecialEquivGroups(self, A: 'List[str]') -> 'int':
    return len({''.join(sorted(s[0::2])) + ''.join(sorted(s[1::2]))
                for s in A})

1003. Check If Word Is Valid After Substitutions

判断字符串是否由abc无限插入得到。原题

1
2
3
4
5
Input: "aabcbc"
Output: true
Explanation: 
We start with the valid string "abc".
Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".
1
2
3
4
5
6
7
8
def isValid(self, S: str) -> bool:
    while len(S) >= 3:
        if 'abc' in S:
            i = S.index('abc')
            S = S[:i] + S[i+3:]
        else:
            return False
    return S == ''

17. Letter Combinations of a Phone Number

电话的数字可以组成的字符串组合。原题

1
2
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

方法一：recursive.

1
2
3
4
5
6
7
8
9
10
11
12
def letterCombinations(self, digits: str) -> List[str]:
    phone = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', 
             '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    if not digits:
        return []

    def helper(digits):
        if not digits:
            return ['']
        return [c + suffix for c in phone[digits[0]]
                for suffix in helper(digits[1:])]
    return helper(digits)

方法二：使用product。

1
2
3
4
5
def letterCombinations(self, digits: str) -> List[str]:
    phone = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', 
             '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    from itertools import product
    return digits and list(map(''.join, product(*(phone[d] for d in digits)))) or []
方法三：实现product。 
1
2
3
4
5
6
7
8
def letterCombinations(self, digits: str) -> List[str]:
    phone = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', 
             '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    ans = ['']
    letters = (phone[d] for d in digits)
    for key in letters:
        ans = [x+char for x in ans for char in key]
    return digits and ans or []
方法四：评论里看到的reduce方法。 
1
2
3
4
5
6
def letterCombinations(self, digits: str) -> List[str]:
    from functools import reduce
    phone = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', 
             '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    if not digits: return []
    return reduce(lambda acc, digit: [x + y for x in acc for y in phone[digit]], digits, [''])

方法五：Solution中的回溯法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def letterCombinations(self, digits: str) -> List[str]:
    phone = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', 
             '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    
    def backtrack(combination, digits):
        if not digits:
            ans.append(combination)
        else:
            for letter in phone[digits[0]]:
                backtrack(combination + letter, digits[1:])
    ans = []
    if digits:
        backtrack('', digits)
    return ans

1023. Binary String With Substrings Representing 1 To N

二进制子串，从1到N。原题

1
2
Input: S = "0110", N = 3
Output: true

方法一：暴力法。

1
2
def queryString(self, S: str, N: int) -> bool:
    return all(bin(n)[2:] in S for n in range(1, N+1))

方法二：对于任意的i<N/2的数i*2的二进制表示形式一定包含i。因为左移一位。

1
2
def queryString(self, S: str, N: int) -> bool:
    return all(bin(n)[2:] in S for n in range(N, N//2, -1))

482. License Key Formatting

根据要求格式化字符串。原题

1
2
Input: S = "5F3Z-2e-9-w", K = 4
Output: "5F3Z-2E9W"

方法一：使用内置方法。

1
2
3
def licenseKeyFormatting(self, S: str, K: int) -> str:
    s = S.replace('-', '').upper()[::-1]
    return '-'.join(s[i:i+K] for i in range(0, len(s), K))[::-1]

方法二：完整实现。one-pass.

1
2
3
4
5
6
7
8
def licenseKeyFormatting(self, S: str, K: int) -> str:
    s = S.replace('-', '').upper()
    ans, n = '', len(s)
    f = n % K
    ans += s[:f]
    for i in range(f, n, K):
        ans += '-' + s[i:i+K]
    return ans.strip('-')

1071. Greatest Common Divisor of Strings

最长公共被整除的字符串。原题

1
2
3
4
5
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

方法一：这里我是从小找一个公共串，并记录重复次数。再从两个重复的次数中取最大公约数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def gcdOfStrings(self, str1: str, str2: str) -> str:
    n1, n2 = len(str1), len(str2)
    from math import gcd

    def repeat(word):
        n = len(word)
        for i in range(1, n//2+1):
            for k in range(i):
                if len({word[j] for j in range(k, n, i)}) != 1:
                    break
            else:
                return word[:i], n // i
        return '', 1
    common1, num1 = repeat(str1)
    common2, num2 = repeat(str2)
    return gcd(num1, num2) * common1
方法二：递归。 
1
2
3
4
5
6
7
8
9
10
def gcdOfStrings(self, str1: str, str2: str) -> str:
    if len(str1) == len(str2):
        return str1 if str1==str2 else ''
    else:
        if len(str1) < len(str2):
            str1, str2 = str2, str1
        if str1[:len(str2)] == str2:
            return self.gcdOfStrings(str1[len(str2):], str2)
        else:
            return ''

1156. Swap For Longest Repeated Character Substring

最多交换一次两个字符，求连续重复的字符最大个数是多少。原题

1
2
3
4
5
6
Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa", which its length is 6.

Input: text = "aaabbaaa"
Output: 4

方法一：竞赛没在规定时间内完成，思路是对的，使用groupby，第二个例子那里小细节没有处理好。

1
2
3
4
5
6
7
8
9
def maxRepOpt1(self, text: str) -> int:
    
    gg = [(d, len(list(g))) for d, g in itertools.groupby(text)]
    count = collections.Counter(text)
    ans = max(min(c+1, count[k]) for k, c in gg)
    for i in range(1, len(gg)-1):
        if gg[i-1][0]==gg[i+1][0] and gg[i][1]==1:
            ans = max(ans, min(gg[i-1][1]+gg[i+1][1]+1, count[gg[i+1][0]]))
    return ans

1106. Parsing A Boolean Expression

转换&|~操作符，返回结果。原题

1
2
Input: expression = "|(&(t,f,t),!(t))"
Output: false

方法一：这题很有意思，马上就能想到用eval来作弊，但是~没有处理好，看了Lee神答案后恍然大悟。这里需要将非符号转成any数组。

1
2
3
4
def parseBoolExpr(self, expression: str) -> bool:
    t, f = True, False
    expression = expression.replace('!', 'not |').replace('&(', 'all([').replace('|(', 'any([').replace(')', '])')
    return eval(expression)

1408. String Matching in an Array

找出字符串是其它子串的字符串。原题

1
2
3
4
Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

方法一：排序暴力法。

1
2
3
4
5
6
7
8
9
def stringMatching(self, words: List[str]) -> List[str]:
    words.sort(key=len)
    ans = []
    for i in range(len(words)-1):
        for j in range(i+1, len(words)):
            if words[i] in words[j]:
                ans.append(words[i])
                break
    return ans

791. Custom Sort String

自定义排序字符串，按照S中字母顺序排序T。原题

1
2
3
4
5
6
7
8
Example :
Input: 
S = "cba"
T = "abcd"
Output: "cbad"
Explanation: 
"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a". 
Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.
1
2
3
4
def customSortString(self, S: str, T: str) -> str:
    # return ''.join(sorted(T, key=S.find))
    d = {k: i for i, k in enumerate(S)}
    return ''.join(sorted(T, key=lambda x: d.get(x, -1)))

678. Valid Parenthesis String

匹配括号，*可以表示左右或者空。原题

1
2
Input: "(*))"
Output: True

方法一：这题一开始想歪了，想用栈和递归的方式实现，结果没想出来。这里用了Lee215的方法。cmin表示至少需要), cmax表示最多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def checkValidString(self, s: str) -> bool:
    cmin = cmax = 0
    for c in s:
        if c == '(':
            cmin += 1
            cmax += 1
        elif c == ')':
            cmax -= 1
            cmin = max(cmin - 1, 0)
        elif c == '*':
            cmax += 1
            cmin = max(cmin - 1, 0)
        if cmax < 0:
            return False
    return cmin == 0

1419. Minimum Number of Frogs Croaking

有n个青蛙🐸一起叫，叫声混到了一起，求最小青蛙的个数。原题

1
2
3
4
5
Input: croakOfFrogs = "crcoakroak"
Output: 2 
Explanation: The minimum number of frogs is two. 
The first frog could yell "crcoakroak".
The second frog could yell later "crcoakroak".

方法一：记录每个字母的个数，注意叫的过程中字母数量的顺序。inuse表示同时叫的青蛙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
    from collections import defaultdict
    c = defaultdict(int)
    inuse = 0
    ans = 0
    for f in croakOfFrogs:
        if f == 'c':
            inuse += 1
        elif f == 'k':
            inuse -= 1
        c[f] += 1
        ans = max(ans, inuse)
        if not c['c'] >= c['r'] >= c['o'] >= c['a'] >= c['k']:
            return -1
    if inuse==0 and len(set(c.values()))==1:
        return ans
    else:
        return -1

1358. Number of Substrings Containing All Three Characters

包含’abc’子串的个数。原题

1
2
3
Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

方法一：滑动窗口。记录abc的数量，当无法组成时退出，此时最左的索引为i-1。

1
2
3
4
5
6
7
8
9
10
def numberOfSubstrings(self, s: str) -> int:
    res = i = 0
    count = {c: 0 for c in 'abc'}
    for j in range(len(s)):
        count[s[j]] += 1
        while all(count.values()):
            count[s[i]] -= 1
            i += 1
        res += i
    return res

方法二：数学方法。以右侧点为准，向左累加。

1
2
3
4
5
6
7
def numberOfSubstrings(self, s: str) -> int:
    res = 0
    last = [-1] * 3
    for i, c in enumerate(s):
        last[ord(c) - 97] = i
        res += 1 + min(last)
    return res

1309. Decrypt String from Alphabet to Integer Mapping

数字到字母的一个映射。原题

1
2
3
Input: s = "10#11#12"
Output: "jkab"
Explanation: "j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".

方法一：比赛时的答案过于繁琐。

1
2
def freqAlphabets(self, s: str) -> str:
    return ''.join(chr(int(i[:2]) + 96) for i in re.findall(r'\d\d#|\d', s))

1545. Find Kth Bit in Nth Binary String

找到第n个字符串的第k位。原题

  • S1 = "0"
  • S2 = "0**1**1"
  • S3 = "011**1**001"
  • S4 = "0111001**1**0110001"
1
2
3
Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001". The first bit is "0".

方法一：比赛时是按照题意的方式写的，效率慢了10倍，这题用逆向思维。by@lee215.

1
2
3
4
5
6
7
8
9
10
11
def findKthBit(self, n: int, k: int) -> str:
    flip = 0
    l = 2 ** n - 1
    while k > 1:
        if k == l // 2 + 1:
            return str(1 ^ flip)
        if k > l // 2:
            k = l + 1 - k
            flip = 1 - flip
        l //= 2
    return str(flip)

777. Swap Adjacent in LR String

转换成目标字符串，可以将”XL”变成”LX”，或者将”RX”变成”XR”。原题

1
2
3
4
5
6
7
8
9
Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
Output: True
Explanation:
We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

方法一：一开始想错了，以为互换倒过来也行。这个变换有点像将L向左移，R向右移，而且不能跨越其它的R或者L也就是可以将X想象成空位。所以这里计算时要将LR一起考虑。

1
2
3
4
5
6
7
8
9
def canTransform(self, start: str, end: str) -> bool:
    left = [(c, i) for i, c in enumerate(start) if c!='X']
    right = [(c, i) for i, c in enumerate(end) if c!='X']
    if len(left) != len(right): return False
    for (c1, i), (c2, j) in zip(left, right):
        if c1 != c2: return False
        if c1 == 'L' and i < j: return False
        if c1 == 'R' and i > j: return False
    return True

539. Minimum Time Difference

两个时间的最小分钟差的绝对值。原题

1
2
Input: ["23:59","00:00"]
Output: 1

方法一：Lee的方法，自己想的一样，优化一下写法。

1
2
3
4
def findMinDifference(self, timePoints: List[str]) -> int:
    time = sorted(int(t[:2])*60+int(t[-2:]) for t in timePoints)
    time.append(time[0]+60*24)
    return min(b-a for a, b in zip(time, time[1:]))

459. Repeated Substring Pattern

字符串中是否包含重复的子串模式。原题

1
2
3
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

方法一：如果s包含一个重复的子串，那么通过旋转s在n-1次之内，一定会又出现s本身。如s='abcabc'那么旋转三次就会得到它。判断是否出现重复那么只要出现两次就算。于是将s+s得到s2。并将头尾去掉，这样s2包含了所有的旋转可能。如果s在其中，那么就说明至少有2次以上的子串重复。

1
2
def repeatedSubstringPattern(self, s: str) -> bool:
    return s in (s * 2)[1:-1]

165. Compare Version Numbers

比较两个版本号，版本的大小。原题

1
2
Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1

方法一：这题写完直接自信提交。

1
2
3
4
5
6
7
8
def compareVersion(self, version1: str, version2: str) -> int:
    v1, v2 = map(int, version1.split('.')), map(int, version2.split('.'))
    for d1, d2 in itertools.zip_longest(v1, v2, fillvalue=0):
        if d1 > d2:
            return 1
        if d2 > d1:
            return -1
    return 0

方法二：学学stefan的写法。其实就是cmp函数，python3没有这个函数。

1
2
3
4
def compareVersion(self, version1: str, version2: str) -> int:
    v1, v2 = map(int, version1.split('.')), map(int, version2.split('.'))
    v1, v2 = zip(*itertools.zip_longest(v1, v2, fillvalue=0))
    return [0, 1, -1][(v1>v2)-(v2>v1)]

1371. Find the Longest Substring Containing Vowels in Even Counts

找到最长的包含偶数个元音字母的字符串，这道题非常的典型。原题

1
2
3
Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

方法一：自己研究了半天的写法，其实感觉2个数组记录属实有点多余。对于变化的形态，一种有32种状态，我这里是记录了这个状态最开始时上个状态+1的索引，因为这种状态可以通过非元音往两侧延伸。然后记录了每种状态最后的索引。结果就是两个索引的差值。

1
2
3
4
5
6
7
8
9
10
11
12
13
def findTheLongestSubstring(self, s: str) -> int:
    vowels = 'aeiou'
    mask = last_mask = 0
    first = [-1] + [float('inf')] * 31
    last = [-1] + [float('-inf')] * 31
    for i, c in enumerate(s):
        if c in set(vowels):
            j = vowels.index(c)
            last_mask, mask = mask, mask ^ (1<<j)
            if first[mask] == float('inf'):
                first[mask] = last[last_mask] + 1 
        last[mask] = i
    return max(j-i for i, j in zip(first, last))
方法二：Lee的写法。思路是一样的，写法上有了改进，setdefault我也想到了，但是last数组没想到怎么消除。原来要每次计算一下。1<<i>>1是为了将其他find为0的变成0。不过大佬的方法比我的慢了200ms，可能因为’aeiou‘的反复遍历。 
1
2
3
4
5
6
7
8
def findTheLongestSubstring(self, s: str) -> int:
    seen = {0: -1}
    res = cur = 0
    for i, c in enumerate(s):
        cur ^= 1 << ('aeiou'.find(c) + 1) >> 1
        seen.setdefault(cur, i)
        res = max(res, i - seen[cur])
    return res

443. String Compression

原地压缩一个字符数组，如果是1则不需要补数量。原题

1
2
3
4
5
6
Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".
Input: chars = ["a","a","a","b","b","a","a"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","3","b","2","a","2"].
Explanation: The groups are "aaa", "bb", and "aa". This compresses to "a3b2a2". Note that each group is independent even if two groups have the same character.

方法一：因为不能使用其它的空间，所以只能是通过指针来改变。0作为一个结尾符号，因为还可能包含其它符号，而不会出现数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def compress(self, chars: List[str]) -> int:
    i, j, cnt, last = 0, 0, 1, ''
    chars.append('0')
    for j, s in enumerate(chars):
        if s == last:
            cnt += 1
        else:
            to_add = last + (str(cnt) if cnt!=1 else '')
            for c in to_add:
                chars[i] = c
                i += 1
            cnt = 1
            last = s
    return i

809. Expressive Words

情感丰富的单词，给定一个单词列表，判断有多少个可以变成S，规则是可以重复一个字母，但是至少要重复到3次。原题

1
2
3
4
5
6
7
8
Example:
Input: 
S = "heeellooo"
words = ["hello", "hi", "helo"]
Output: 1
Explanation: 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.

方法一：首次AC的方法，groupby注意只能遍历一次，哪怕是求len，也会导致其中嵌套的生成器被消耗掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def expressiveWords(self, S: str, words: List[str]) -> int:
    ans = 0
    for word in words:
        sg = itertools.groupby(S)
        wg = itertools.groupby(word)
        for (sc, sgs), (wc, wgs) in itertools.zip_longest(
            sg, wg, fillvalue=('0', None)):
            if sc != wc: break
            cnt_s, cnt_w = len(list(sgs)), len(list(wgs))
            if (cnt_s==2 and cnt_w==1) or (cnt_s<cnt_w):
                break
        else:
            ans += 1
    return ans
方法二：solution中的方法，和我的思想一样，但是我的写法没有这个好。首先遍历一次然后记录个数就行了，所以为什么要遍历很多次呢，再一个判断时使用满足+1，就可以避免使 用zip_longest。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def expressiveWords(self, S: str, words: List[str]) -> int:
    
    def rle(s):
        return zip(*[(k, len(list(grp)))
                    for k, grp in itertools.groupby(s)])
    
    if not S: return 0
    R, count = rle(S)  # [('h', 'e', 'l', 'o'), (1, 3, 2, 3)]
    ans = 0
    for word in words:
        R2, count2 = rle(word)
        if R != R2: continue
        ans += all(c1>=max(c2, 3) or c1==c2
                  for c1, c2 in zip(count, count2))
    return ans

833. Find And Replace in String

找到匹配并替换，注意是所有的同时替换，因为替换长度不同可能会导致索引不一致，所以不能用切片直接修改。原题

1
2
3
4
Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it's replaced by "eee". 
"ec" doesn't starts at index 2 in the original S, so we do nothing.

方法一：注意last_i要更新，还有一点是，islice用的不熟，以为islice(S, 0)是从0开始呢，原来是到0截止。

1
2
3
4
5
6
7
8
9
10
def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
    ans, last_i = [], 0
    for i, r, t in sorted(zip(indexes, sources, targets)):
        ans.append(S[last_i:i])
        last_i, j = i, len(r)
        if all(c1==c2 for c1, c2 in zip(itertools.islice(S, i, i+j), r)):
            ans.append(t)
            last_i += j
    ans += S[last_i:]
    return ''.join(ans)
方法二：by Lee215，我看了一眼就写出来了，直接使用了切片，因为逆序不影响索引。理论上方法一要快一点，因为没有产生多余的切片，但实际上二者时间相差无几。 
1
2
3
4
def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
    for i, r, t in sorted(zip(indexes, sources, targets), reverse=True):
        S = S[:i] + t + S[i+len(r):] if S[i:i+len(r)]==r else S
    return S
方法三：倒序改方法一。 
1
2
3
4
5
6
7
def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
    s = list(S)
    for i, r, t in sorted(zip(indexes, sources, targets), reverse=True):
        j = len(r)
        if all(c1==c2 for c1, c2 in zip(itertools.islice(s, i, i+j), r)):
            s[i:i+j] = t
    return ''.join(s)

面试题 17.15. 最长单词

给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

方法一：dfs。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longestWord(self, words: List[str]) -> str:
    words.sort(key=lambda w: (-len(w), w))
    N = len(words)

    def gen_word(cur, w):
        if not w:
           return True
        for word in words:
            if w.startswith(word) and word!=cur:
                if gen_word(cur, w[len(word):]):
                    return True
        return False

    return next((word for word in words if gen_word(word, word)), '')
    # return next(word for word in words if gen_word(word, word))
    # 这句话不行，会导致没有任何输出，而且还会影响别的用例。和输出顺序有关。

面试题 16.18. 模式匹配

你有两个字符串，即pattern和value。 pattern字符串由字母”a”和”b”组成，用于描述字符串中的模式。例如，字符串”catcatgocatgo”匹配模式”aabab”（其中”cat”是”a”，”go”是”b”），该字符串也匹配像”a”、”ab”和”b”这样的模式。但需注意”a”和”b”不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

方法一：这题边界条件挺多的。写了很长时间。不是最优的时间复杂度，但是速度还可以。

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
def patternMatching(self, pattern: str, value: str) -> bool:
    N, M = len(pattern), len(value)
    first, first_val = pattern[0], ''
    another = 'ab'[first=='a']
    cnt_another = pattern.count(another)
    for c in (value + '#'):
        # print(first_val)
        if cnt_another == 0:
            len_another = 0
            another_val = ''
        else:
            len_another = (M - (len(first_val)*(N-cnt_another))) / cnt_another
            if not len_another.is_integer():  # 不能整除则跳过
                first_val += c
                continue
            else:
                len_another = int(len_another)
            j = pattern.find(another)
            another_val = value[j*len(first_val):j*len(first_val)+len_another]

        if (pattern.replace(another, '#').replace(first, first_val).replace('#', another_val)==value) and (cnt_another==0 or first_val!=another_val):
            return True
        first_val += c

    return False

1638. Count Substrings That Differ by One Character

两个字符串的连续子串中刚好差一个字符的一共有多少对。

1
2
3
4
5
6
7
8
9
10
11
12
Input: s = "aba", t = "baba"
Output: 6
Explanation: The following are the pairs of substrings from s and t that differ by exactly 1 character:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
The underlined portions are the substrings that are chosen from s and t.
Input: s = "abe", t = "bbc"
Output: 10

方法一: 比赛时暴力过的。复杂度很高，时间1000ms+，不过居然能过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def countSubstrings(self, s: str, t: str) -> int:
    
    def check(s1, s2):
        count = 0
        for a, b in zip(s1, s2):
            if a != b:
                count += 1
            if count == 2:
                return False
        return count == 1
        
    min_len = min(len(t), len(s))
    ans = 0
    for d in range(1, min_len+1):
        for i in range(len(s)-d+1):
            s1 = s[i:i+d]
            for j in range(len(t)-d+1):
                s2 = t[j:j+d]
                # print(s1, s2, check(s1, s2))
                ans += check(s1, s2)
    return ans
方法二：Lee的方法好太多了，44ms。当字符不相等时重置为0，否则累加。这个写法挺难理解的，cur表示相等的数的累加，不相等时重置为0，然后交给pre来处理。 
1
2
3
4
5
6
7
8
9
10
11
12
13
def countSubstrings(self, s: str, t: str) -> int:
    M, N = len(s), len(t)
    
    def check(i, j):
        res = pre = cur = 0
        for k in range(min(M-i, N-j)):
            cur += 1
            if s[i+k] != t[j+k]:
                pre, cur = cur, 0
            res += pre
        return res
    
    return sum(check(i, 0) for i in range(M)) + sum(check(0, j) for j in range(1, N))