Leetcode 刷题笔记1: String 类型题汇总

发布于 2023-04-23  209 次阅读


Let's start with some basic (not that basic) operations on String by Python:

  1. Stack!!!

You should be aware that Most of the String problems is associate with stack!

That's right! sometimes we tend to use operations quite similar to compiler, thus we need to be familiar with everything in STACK

Stack operations

stack = []
# push into stack
stack.append(1)  # [1]
stack.append(2)  # [1, 2]
stack.append(3)  # [1, 2, 3]
# pop out the top element
top = stack.pop() # top = 3, stack -> [1, 2]
# get the top element
top = stack[-1] # top = 2, stack -> [1, 2]  (similar to peek)

But in fact, how we use python queue in leetcode problem is that:
a) We use head-tail linked list (deque):

from collections import deque
de1 = deque()
de1.append(1) # [1]
de1.append(2) # [1, 2]
de1.appendleft(5) # [5, 1, 2]
de1.appendleft(6) # [6, 5, 1, 2]
print(de1.count(1)) # 1 appears 1
de1.reverse() # [2, 1, 5, 6]
de1.extend([444, 555, 666]) # [2, 1, 5, 6, 444, 555, 666]
de1.pop() # [2, 1, 5, 6, 444, 555]
de1.popleft() # [1, 5, 6, 444, 555]

b) Priority queue:

import queue
q = queue.Queue()
q.put(3)
q.put(5)
q.put(4)
full = q.full() # True
while not q.empty():
    print(q.get()) # [3, 5, 4]

# min first
pq = queue.PriorityQueue()
pq.put(3)
pq.put(5)
pq.put(4)
while not pq.empty():
    print(pq.get()) # [3, 4, 5]

# max first
pq = []
pq.append(3)
pq.append(5)
pq.append(4)
pq.sort(reverse=1)
while pq:
    print(pq.pop())

By the way, we should know how to implement a queue through 2 stack, which will be push = O(1) and pop = O(1)

This is the problem of Leetcode 232:

class MyQueue:
    def __init__(self):
        self.LI = []  # Last In
        self.FO = []  # First Out

    def push(self, x):
        self.LI.append(x)

    def pop(self):
        if not self.FO:
            while self.LI:
                self.FO.append(self.LI.pop())
        return self.FO.pop()

    def peek(self):
        if not self.FO:
            return self.LI[0]
        else:
            return self.FO[-1]

    def empty(self):
        return not self.LI and not self.FO

Or if we want one stack to represent queue, it is also OK!

class MyQueue(object):
    def __init__(self):
        self.st = []

    def push(self, x):
        if len(self.st) == 0:
            self.st.append(x)
            return
        tmp = self.st.pop(-1)
        self.push(x)
        self.st.append(tmp)

    def pop(self):
        return self.st.pop(-1)

    def peek(self):
        return self.st[-1]

    def empty(self):
        return len(self.st) == 0
  1. Reverse String:
ori_str = "abcd"
reverse_str = ori_str[::-1] #come to "dcba"
  1. Find SubString:

    super_str = "abcde"
    sub_str = "bc"
    not_sub_str = "abd"
    pos = super_str.find(sub_str) #pos = 1, find from beginning
    pos_2 = super_str.rfind(sub_str) # pos_2 = 1, find from the rear
    pos_3 = super_str.find(not_sub_str) # pos_2 = -1, not substring found
  2. index & count

    ori_str = "abcde"
    pos = ori_str.index("c") # pos = 2
    pos_1 = ori_str.rindex("b") # pos_1 = 1
  3. count

    ori_str = "abcdeaa"
    num = ori_str.count("a") # num = 3
    num_1 = ori_str.count("a", 0, 3) # num_1 = 1
  4. Split, Partition, Split with line

    
    str = "123123123"               
    str_list = str.split('2') # ['1', '31', '31', '3']          
    str_tuple = str.partition('2')  # ('1', '2', '3123123')     

str='abc\nabc\nabc\nabc'
str_list = str.splitlines() # ['abc', 'abc', 'abc', 'abc']

6. Judgement
```python
str0='0123abcd'
str1='12345'
str2='abcdef'
str3='    '

str0.startswith('0')    # check if start with 0, True
str0.endswith('0')      # check if end with 0, False

str1.isalnum()        # check if the str all consist of alphabet and number, True
str2.isalpha()        # check if the str all consist of alphabet, True
str0.isdigit()        # check if the str all consist of digit, False
str3.isspace()    # check if all consist of space, True
  1. ATTENTION: String cannot be changed, but we can change by..

    str0 = "what"
    # str0[2] = "i" # This is not allowed!!!
    list_str0 = list(str0)
    list_str0[2] = "i"
    str0 = "".join(list_str0)
    print(str0)
  2. Mapping

    date = "2019-8-15"
    Y, M, D = map(int, date.split('-'))
    # Y = 2019, M = 8, D = 15

Leetcode

242. Valid Anagram

Description: return true if s is an anagram of t

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

Solution 1 with Collections (inner Hash Map):

def isAnagram(self, s: str, t: str) -> bool:
    from collections import Counter
    # Counter(s) = Counter({'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1})
    return Counter(s) == Counter(t)

Solution 2 with HashMap (By ourself) in O(n):

def isAnagram(self, s: str, t: str) -> bool:
    map1 = {}

    if s == '' and t == '':
        return True
    if len(s) != len(t):
        return False
    for itr in range(len(s)):
        map1[s[itr]] = map1.setdefault(s[itr], 0) + 1
        map1[s[itr]] = map1.setdefault(t[itr], 0) + 1
    for i in map1.values():
        if i != 0:
            return False
    return True
409. Valid Anagram

Solution 1 with Hash Map:

def longestPalindrome(self, s: str) -> int:
    map1 = {}
    for item in range(len(s)):
        map1[s[item]] = map1.setdefault(s[item], 0) + 1
    res = 0    
    for item in map1.values():
        res += (item // 2) * 2
    if res < len(s):
        res += 1
    return res
205. Isomorphic Strings

Description:
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

Solution 1 with find function:

def isIsomorphic(self, s, t):
    # e.g. s = "eggggwe"
    # [s.find(i) for i in s] = [0, 1, 1, 1, 1, 5, 0]
    return [s.find(i) for i in s] == [t.find(j) for j in t]

Solution 2 with dict function:

def isIsomorphic(self, s, t):
    if len(s) != len(t): return False
    map1 = {}
    for i in range(len(s)):
        if s[i] in map1:
            if map1[s[i]] != t[i]:
                return False
        elif t[i] in map1.values():
            return False
        else:
            map1[s[i]] = t[i]
    return True
647. Palindromic Substrings
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Solution 1 with find function:

res = 0
def countSubstrings(self, s: str) -> int:
    for i in range(len(s)):
        self.extension(s, i, i);
        self.extension(s, i, i+1);
    return self.res

def extension(self, s: str, start: int, end: int):
    while start >= 0 and end <= len(s) - 1 and s[start] == s[end]:
        start -= 1
        end += 1
        self.res += 1
9. Palindrome Number
Input: x = 121
Output: true

Input: x = -121
Output: false

Could you solve it without converting the integer to a string?

Solution 1 simple implement:

def isPalindrome(self, x: int) -> bool:
    if x < 0 or (x > 0 and x % 10 == 0): return False
    ori = x
    res = 0

    while x != 0:
        digit = x % 10
        x = x // 10
        res = digit + res * 10

    return ori == res

Solution 2 with half loop:

def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x > 0 and x % 10 == 0): return False
        right = 0
        while x > right:
            right = right * 10 + x % 10
            x = x // 10 
        return x == right or x == right // 10
696. Count Binary Substrings
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".

Solution 1 with group by character:

    def countBinarySubstrings(self, s: str) -> int:
        groups = [1]
        for i in range(1, len(s)):
            if s[i] != s[i - 1]:
                groups.append(1)
            else:
                groups[-1] += 1

        ans = 0
        for i in range(1, len(groups)):
            ans += min(groups[i-1], groups[i])
        return ans

Solution 1 with linear scanning, not using a list, but use two var to store pre and cur:

def countBinarySubstrings(self, s: str) -> int:
    preLen, curLen, count = 0, 1, 0
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            curLen += 1
        else:
            preLen = curLen
            curLen = 1

        if preLen >= curLen:
            count += 1
    return count

rGdjF0f

一个平静且愿意倾听的人。
最后更新于 2023-07-17