Introduction to String

本文蒐集

• LeetCode 67
• LeetCode 28
• LeetCode 14

LeetCode 67: Add Binary

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Constraints :

• 1 <= a.length, b.length <= \(10^4\)
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

我的解法 1

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        if a == '0':
            return b
        elif b == '0':
            return a
        else:
            ans = deque()
            s = int(a) + int(b)
            temp = 0
            
            while s != 0:
                ans.append((s+temp) % 2)
                if (s+temp) % 10 >= 2:
                    temp = 1
                else:
                    temp = 0
                s //= 10
            if temp == 1:
                ans.append(1)
        s = ''    
        for i in range(len(ans)):
            s += str(ans.pop())
        return s

我的解法 2

遞迴式寫法

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        if len(a)==0: return b
            if len(b)==0: return a
            if a[-1] == '1' and b[-1] == '1':
                return self.addBinary(self.addBinary(a[0:-1],b[0:-1]),'1')+'0'
            if a[-1] == '0' and b[-1] == '0':
                return self.addBinary(a[0:-1],b[0:-1])+'0'
            else:
                return self.addBinary(a[0:-1],b[0:-1])+'1'

LeetCode 28: Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Example 3:

Input: haystack = "", needle = ""
Output: 0

Constraints : - 0 <= haystack.length, needle.length <= 5 * \(10^4\) - haystack and needle consist of only lower-case English characters.

我的解法 1

while 方法 1

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == '':
            return 0
        
        i = 0
        while i < len(haystack)-len(needle)+1:
            j, k, flag = 0, i, 0
            
            while j < len(needle) and k < len(haystack):
                if haystack[k] != needle[j]:
                    break
                k += 1
                j += 1
                if j == len(needle):
                    return i
            i += 1
        return -1

我的解法 2

while 方法 2

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(haystack) < len(needle): # early termination
            return -1
        if not needle:
            return 0
    
        i = j = 0
        while j < len(needle) and i < len(haystack): 
            if haystack[i] != needle[j]:
                i = i - j + 1
                j = 0
                continue 
            i += 1
            j += 1
        return i - j if j == len(needle) else -1

我的解法 3

for

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == '':
            return 0
        for i in range(len(haystack)-len(needle)+1):
    	    if haystack[i:i+len(needle)] == needle:
                return i
        return -1

我的解法 4

KMP 演算法

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def kmp(str_):
            b, prefix = 0, [0]
            for i in range(1, len(str_)):
                while b > 0 and str_[i] != str_[b]:
                    b = prefix[b - 1]
                if str_[b] == str_[i]:
                    b += 1
                else:
                    b = 0
                prefix.append(b)
            return prefix

        str_ = kmp(needle + '#' + haystack)
        n = len(needle)
        if n == 0:
            return n
        for i in range(n + 1, len(str_)):
            if str_[i] == n:
                return i - 2 * n
        return -1

LeetCode : Longest Common Prefix

Example : Constraints : Follow-up :

我的解法