過年期間哆料，筆者實在無聊，而且年后要找關(guān)于數(shù)據(jù)方面的實習策添，就用了大概3天空閑時間二刷了leetcode的string題目材部。截止筆者寫此篇日志，關(guān)于string的題目一共有55道唯竹，easy+medium免費公開的題目共30道乐导，筆者做了其中的27道，我就將我所做的28道題目的題解以及自己的一些想法留在簡書這個平臺浸颓。由于并不是什么算法大牛物臂，所以我會不斷調(diào)整代碼。
PS：筆者用的語言是python产上，筆者的目的更多的是實現(xiàn)功能棵磷，因此有些題目也就因為是python就偷懶了，有機會再把性能更好的代碼貼出來晋涣。

3. Longest Substring Without Repeating Characters

題目：給一個長字符串s尋找最長的子字符串仪媒，該字符串內(nèi)沒有重復的字符。
思路：遍歷長字符串谢鹊，當字符在子字符串出現(xiàn)算吩，首先比較原子字符串是否是目前最長子字符串留凭，如果是將長度存在count中；然后偎巢，找到子字符串重復字符位置蔼夜，該位置的下一個位置就是新子字符串開始的位置。
注意：
（1）str.find(ch)的使用压昼，返回第一個匹配位置求冷，否則返回。
（2）循環(huán)結(jié)束需要再次算長度巢音，初學者容易忘記遵倦。

def lengthOfLongestSubstring(self, s):
    """
    :type s: str
    :rtype: int
    """
    count = 0
    tmp_str = ""
    
    for ch in s:
        if ch in tmp_str:
            count = max(count,len(tmp_str))
            tmp_str = tmp_str[tmp_str.find(ch)+1:]
        tmp_str += ch
    count = max(count,len(tmp_str))
    return count

5. Longest Palindromic Substring

題目：尋找字符串中的最長回文字字符串。
思路：回文字符串有兩種官撼，因此我們要分兩種情況梧躺，分別是“AA”和“ABA”。遍歷長字符串傲绣，看是否滿足兩種情況掠哥，如果滿足就像兩個方向上延伸，并記錄最長的那個子回文字符串秃诵。
注意：
（1）邊界的判斷
（2）我在s字符串后加了一個空格' '续搀。目的是人工創(chuàng)建了一個邊界而不影響原字符串的特征，這樣我就可以不用檢測右側(cè)邊界了菠净。

def longestPalindrome(self, s):
    """
    :type s: str
    :rtype: str

    """
    result= s[0]
    s = s+' '
    for num,ch in enumerate(s[:-1]):
        if ch == s[num+1]:
            point,len_pal = num,1
            while point+1-len_pal !=-1  and s[point+1-len_pal] == s[point+len_pal]:len_pal+=1
            len_pal-=1
            if len(result) <= len_pal*2 : result = s[point+1-len_pal:point+len_pal+1]
        if num-1!=-1 and s[num-1] == s[num+1]:
            point,len_pal = num,1
            while point-len_pal !=-1 and s[point+len_pal] == s[point-len_pal]:len_pal+=1
            len_pal-=1
            if len(result) <= len_pal*2+1 : result = s[point-len_pal:point+1+len_pal]             
    return result

6. ZigZag Conversion

題目：

P A H N
A P L S I I G
Y I R

用字符串表示為"PAHNAPLSIIGYIR"禁舷，我們要寫一個函數(shù)，函數(shù)的功能如下：

convert("PAYPALISHIRING", 3)
return "PAHNAPLSIIGYIR"

思路：這個題目主要就是找到回形針模式下字符串的規(guī)律毅往，將給的字符串進行三部分處理：第一行牵咙，中間數(shù)行，最后一行攀唯。原因很簡單洁桌，只有中間數(shù)行在一次回形針模式輸出中輸出兩次。數(shù)學規(guī)律并不難找侯嘀，參考代碼即可另凌。
注意：
（1）T是一個循環(huán)周期有多少字符數(shù)，row是處理回形針模式內(nèi)的所在行戒幔，offset是字符所在位置吠谢。
（2）中間行也可能輸出一次，出現(xiàn)這種情況只能是在最后一個不完整的周期內(nèi)诗茎。

def convert(self, s, numRows):
    """
    :type s: str
    :type numRows: int
    :rtype: str
    """
    if numRows == 1 or not s : return s
    
    T,row,offset= (numRows-2)*2+2,1,0
    result = ""
    for offset in range(0,len(s),T):result+=s[offset]
    while(numRows - row -1):
        for offset in range(row,len(s),T):result = result+s[offset]+s[offset+T-2*row] \
        if offset+T-2*row < len(s) else result+s[offset]
        row+=1
    for offset in range(numRows-1,len(s),T):result+=s[offset]
    return result

8. String to Integer (atoi)

12. Integer to Roman

題目：將整型數(shù)字轉(zhuǎn)化為羅馬數(shù)字（字符串）囊卜。
思路：暴力蛤希表，羅馬數(shù)字的規(guī)則請自行百度谷歌错沃。暴力代碼如下（碼的挺累的）
注意：哈希表中加入0這個元素栅组，可以有效地減少代碼量。
補充：/和//的區(qū)別枢析。如果除數(shù)與被除數(shù)都是整型玉掸，結(jié)果是一樣的。問題出在如果除數(shù)為浮點數(shù)醒叁，那么結(jié)果雖然同為浮點數(shù)司浪，但/的結(jié)果是向下取整，而//的結(jié)果是四舍五入把沼。

def intToRoman(self, num):
    """
    :type num: int
    :rtype: str
    """
    dict={0:"",1:"I",2:"II",3:"III",4:"IV",5:"V",6:"VI",7:"VII",8:"VIII",9:"IX",\
    10:"X",20:"XX",30:"XXX",40:"XL",50:"L",60:"LX",70:"LXX",80:"LXXX",90:"XC",\
    100:"C",200:"CC",300:"CCC",400:"CD",500:"D",600:"DC",700:"DCC",800:"DCCC",900:"CM",\
    1000:"M",2000:"MM",3000:"MMM"}
    
    result = ""
    for i in range(3,-1,-1):
        tmp = num/(10**i)
        result += dict[tmp*(10**i)]
        num %=10**i
    return result

13. Roman to Integer

題目：將羅馬數(shù)字（字符串）轉(zhuǎn)化為整型數(shù)字啊易。
思路：當羅馬數(shù)字5，50饮睬，500左側(cè)出現(xiàn)1租谈，10，100是右減左捆愁，其他都是順次做加法割去。因此，代碼如下昼丑。

def romanToInt(self, s):
    """
    :type s: str
    :rtype: int
    """
    roman = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}
    z = 0
    for i in range(0, len(s) - 1):
        if roman[s[i]] < roman[s[i+1]]:
            z -= roman[s[i]]
        else:
            z += roman[s[i]]
    return z + roman[s[-1]]

14. Longest Common Prefix

題目：尋找字符串數(shù)組中最長的公共前綴
思路：遍歷數(shù)組即可呻逆。

def longestCommonPrefix(self, strs):
    """
    :type strs: List[str]
    :rtype: str
    """
    result = strs[0] if strs else ""
    for str in strs:
        for num in range(min(len(str),len(result))):
            if str[num]!=result[num]:
                result = result[:num]
                break
        result = result[:min(len(str),len(result))]
        if not result: return ""
    return result

17. Letter Combinations of a Phone Number

題目： 給一個數(shù)字字符串，返回所有可能的字符串組合（數(shù)字與字符的映射關(guān)系參照手機）
思路：建立一個哈希表菩帝，用以表示數(shù)字和字母間的映射關(guān)系咖城。主體是兩個循環(huán)，第一個循環(huán)的給定字符串中的數(shù)字呼奢，第二個循環(huán)是相應(yīng)數(shù)字的不同字符宜雀。
注意：拷貝方式，這里我們用result = tmp[:]用以表示result拷貝tmp內(nèi)的所有內(nèi)容控妻，而不是兩個變量都指向同一個數(shù)組地址州袒，否則改變?nèi)魏我粋€變量，數(shù)組的改變都是聯(lián)動的弓候。

def letterCombinations(self, digits):
    """
    :type digits: str
    :rtype: List[str]
    """
    if not digits: return []
    dict = {1:"*",2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz",0:" "}
    result = [""]
    for digit in digits:
        tmp = []
        for ch in dict[int(digit)]:
            tmp += [element+ch for element in result]
        result = tmp[:]
    return result

20. Valid Parentheses

題目：給一個字符串只包含'(', ')', '{', '}', '[' 和 ']'郎哭，問字符串是否符合閉合規(guī)則。
思路：標準棧的題目菇存，只要處理好進棧和出棧的順序即可夸研。
注意：如何數(shù)組為空，調(diào)用list.pop()會報錯依鸥。

def isValid(self, s):
    """
    :type s: str
    :rtype: bool
    """
    dict= {"(":")","[":"]","{":"}"}
    
    stack = ["0"]
    
    for ch in s:
        if ch in dict : stack.append(dict[ch])
        else:
            if not ch == stack.pop(): return False
    return True if stack ==["0"] else False

22. Generate Parentheses

題目：給定n組括號（）亥至，將所有括號的組合列舉出來。比如n=3:

["((()))","(()())","(())()","()(())","()()()]

思路：標準的回溯算法題目。

def helper(self, part, left, right, result):
    if left: self.helper(part+'(', left-1, right, result)
    if right > left: self.helper(part+')', left, right-1, result)
    if not right: result.append(part)
    return result
def generateParenthesis(self, n):
    """
    :type n: int
    :rtype: List[str]
    """
    return self.helper("",n,n,[])

28. Implement strStr()

題目：在一個字符串中找一個與給定值相等的字符串姐扮。
思路：暴力遍歷絮供，我們直接進行了字符串比較而不是字符比較，所以損失些性能茶敏，但寫起來更簡單壤靶。

def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """
    if not len(needle) : return 0
    if len(needle) > len(haystack) : return -1
    for num in range(len(haystack[:len(haystack)-len(needle)+1])):
        print num
        if haystack[num:num+len(needle)] == needle:return num
    return -1

38. Count and Say

題目：給一個整數(shù)n，按照下面規(guī)律找第n個序列惊搏。

1 被讀作 "one 1" or 11.
11 被讀作 "two 1s" or 21.
21 被讀作 "one 2, 然后 one 1" or 1211.

思路：以“1”開始循環(huán)n-1次贮乳，用count變量計數(shù)，遇到前后不相等的情況就更新數(shù)據(jù)恬惯，從而得到最后序列向拆。
注意：在result后面加0，0不可能與之前的數(shù)字相等酪耳，所以當循環(huán)的下一個為0時浓恳，一定會調(diào)用else里面的內(nèi)容，這樣可以減少代碼量葡兑。

def countAndSay(self, n):
    """
    :type n: int
    :rtype: str
    """
    result = "1"
    
    for i in range(n-1):
        count,tmp = 1,""
        result+="0"
        for ch in range(len(result[:-1])):
            if result[ch] == result[ch+1]: count+=1
            else:
                tmp = tmp+str(count)+result[ch]
                count = 1
        result = tmp[:]
    return result

43. Multiply Strings

作為python選手奖蔓，我就先不想那么多。讹堤。吆鹤。。洲守。

def multiply(self, num1, num2):
    """
    :type num1: str
    :type num2: str
    :rtype: str
    """
    return str(int(num1)*int(num2))

49. Group Anagrams

題目：對同字母異序詞進行分類疑务。
思路：說話講，這道題目我參考了discuss區(qū)大神的解法梗醇，所以在這里注明下知允，代碼十分簡潔。其實主要就是幾次基于原有列表的排序叙谨。sorted(strs, key=sorted)根據(jù)列表中每一個自排序后的字符串進行排序温鸽，比如：

input: ["a","da","c"]
output:["a","da","c"]

itertools.groupby(list, sorted)的意思是按照排序進行分組，所以比如說"abb","bab"就是存在同一個二級列表中手负。sorted(members)的意義是對二級列表內(nèi)元素進行排序涤垫。代碼如下：

def groupAnagrams(self, strs):
    """
    :type strs: List[str]
    :rtype: List[List[str]]
    """
    groups = itertools.groupby(sorted(strs, key=sorted), sorted)
    return [sorted(members) for _, members in groups]

58. Length of Last Word

題目：找一個字符串中的最后一個單詞的長度。
思路：先把兩端的空格刪去竟终，然后從最后一個字符開始統(tǒng)計蝠猬，遇到空格就跳出循環(huán)，返回正確值统捶。

def lengthOfLastWord(self, s):
    """
    :type s: str
    :rtype: int
    """
    s = s.strip()
    if not s : return 0
    count = 0
    for ch in s[::-1]:
        if ch !=' '  : count+=1
        else : break
    return count

67. Add Binary

題目：兩個二進制數(shù)相加榆芦。
思路：python玩家不要多想柄粹，直接調(diào)用函數(shù)就好。
注意：bin轉(zhuǎn)換后匆绣，得到的是字符串驻右，格式："0bXXXXX"，所以要[2:]

def addBinary(self, a, b):
    """
    :type a: str
    :type b: str
    :rtype: str
    """
    return bin(int(a,2)+int(b,2))[2:]

71. Simplify Path

題目：化簡所給路徑為絕對路徑
思路：將原字符串按斜杠進行分割成一個列表犬绒。然后借助棧來處理旺入。".."代表著pop()；"."代表著無操作凯力。最后再將結(jié)果join成字符串。

def simplifyPath(self, path):
    """
    :type path: str
    :rtype: str
    """
    path_list = path.split("/")
    stack= []
    for str in path_list:
        if not str.strip() or str.strip() == "." or(str.strip() == ".." and not stack): continue
        elif str.strip() == ".." and stack: stack.pop()
        else: stack.append(str)
    return '/'+'/'.join(stack)

91. Decode Ways

題目：

'A' -> 1
'B' -> 2
...
'Z' -> 26

給一個數(shù)字礼华，問有多少種解讀方式咐鹤。
思路：主體思路是動態(tài)規(guī)劃。然后就是對情況的總結(jié)圣絮，順次5種情況祈惶，先后順序一定要注意。

def numDecodings(self, s):
    """
    :type s: str
    :rtype: int
    """
    if not len(s) : return 0
    DP = [1,1]
    s = "0"+s
    
    for num in range(1,len(s),1):
        tmp = int(s[num-1:num+1])
        if tmp ==10 or tmp ==20: DP.append(DP[-2])
        elif not tmp%10 : return 0
        elif tmp<10: DP.append(DP[-2])
        elif tmp>10 and tmp<27:DP.append(DP[-2]+DP[-1])
        else: DP.append(DP[-1])
    return DP[-1]

93. Restore IP Addresses

題目：給一個只包含數(shù)字的字符串扮匠。將其不同的IP組合存入一個列表中捧请。

"25525511135"
["255.255.11.135", "255.255.111.35"]

思路：標準的動態(tài)規(guī)劃+回溯法。當連續(xù)順次的4個數(shù)字字符串能夠組合且不多余數(shù)字的時候棒搜，就是一個合格的子答案疹蛉。所有的答案都儲存在列表中。
注意：不能有以0為開頭的數(shù)字力麸。

def restoreIpAddresses(self, s):
    """
    :type s: str
    :rtype: List[str]
    """
    result = []
    if len(s) > 15: return result
    self.helper(4,s,"",result)
    return result
    
def helper(self,n,new_s,tmp_result,result):
    if n == 0 and len(new_s) == 0:
        result.append(tmp_result[1:])
    for i in range(3): 
        if i < len(new_s) and int(new_s[:i+1]) < 256:
            self.helper(n-1,new_s[i+1:],tmp_result+'.'+new_s[:i+1],result)
            if new_s[0] == "0" : break
        else: break

未完待續(xù)