六. 字符串

14. 最長公共前綴

題目：編寫一個函數(shù)來查找字符串數(shù)組中的最長公共前綴。
輸入：strs = ["flower","flow","flight"]
輸出："fl"

    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0: # 字符串數(shù)組為空
            return ""
        if len(strs) == 1: # 字符串數(shù)組只有一個元素
            return strs[0]
        for j in range(0, len(strs[0])): # 第一個元素的0~j位
            for i in range(1, len(strs)): # 0~i個元素
                if len(strs[i])>=j+1:                   
                    if strs[0][j] != strs[i][j]: 
                        return strs[0][0: j] # 一旦返現(xiàn)第j位有異樣，返回0到j-1位
                    if (j == len(strs[0])-1 and i == len(strs)-1):
                        return strs[0][0:j+1] # 循環(huán)到最后都滿足，返回第0個字符串
                else:                  
                    return strs[0][0: j]
        
        return ""

28. 實現(xiàn) strStr()

題目：給你兩個字符串 haystack 和 needle ，請你在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置（下標從 0 開始）。如果不存在，則返回 -1 。
輸入：haystack = "hello", needle = "ll"
輸出：2
思考：KMP問題。

    def strStr(self, haystack: str, needle: str) -> int:
        a = len(needle)
        b = len(haystack)
        if a == 0:
            return 0
        next = self.getnext(a, needle)
        p = -1
        for j in range(b):
            while p >= 0 and needle[p+1] != haystack[j]:
                p = next[p]
            if needle[p+1] == haystack[j]:
                p += 1
            if p == a-1:
                return j-a+1
        return -1

    def getnext(self, a, needle):
        next=['' for i in range(a)]
        k = -1
        next[0] = k
        for i in range(1,len(needle)):
            while (k >- 1 and needle[k+1] != needle[i]):
                k = next[k]
            if needle[k+1] == needle[i]:
                k += 1
            next[i] = k
        return next

58. 最后一個單詞的長度

題目：最后一個單詞的長度
輸入：s = "Hello World"
輸出：5

    def lengthOfLastWord(self, s: str) -> int:
        flag = 0 # 0 表示還沒遇到字母, 第一次遇到字母后置1
        count = 0
        for x in s[::-1]:
            if x == " " and flag == 0:
                count = 0
            elif x == " " and flag == 1:
                return count
            else:
                flag = 1 # 冗余
                count += 1
        return count

125. 驗證回文串

題目：驗證回文串

    def isPalindrome(self, s: str) -> bool:
        sgood = "".join(ch.lower() for ch in s if ch.isalnum()) # 去除空格和符號
        n = len(sgood)
        left, right = 0, n - 1
        
        while left < right: # 左右逼近
            if sgood[left] != sgood[right]:
                return False
            left, right = left + 1, right - 1
        return True

205. 同構(gòu)字符串

題目：同構(gòu)字符串
輸入：s = "egg", t = "add"
輸出：True

    def isIsomorphic(self, s: str, t: str) -> bool:

        ds = dict()
        dt = dict()
        for i in range(0, len(s)):
            if s[i] in ds: # 存在，檢查ds
                if t[i] != ds[s[i]]:
                    return False       
            elif t[i] in dt: # 存在，檢查dt
                if s[i] != dt[t[i]]:
                    return False
            else: # 不存在，則更新ds和dt
                ds[s[i]] = t[i]
                dt[t[i]] = s[i]
        return True