过年期间，笔者实在无聊，而且年后要找关于数据方面的实习，就用了大概3天空闲时间二刷了leetcode的string题目。截止笔者写此篇日志，关于string的题目一共有55道，easy+medium免费公开的题目共30道，笔者做了其中的27道，我就将我所做的28道题目的题解以及自己的一些想法留在简书这个平台。由于并不是什么算法大牛，所以我会不断调整代码。
PS：笔者用的语言是python，笔者的目的更多的是实现功能，因此有些题目也就因为是python就偷懒了，有机会再把性能更好的代码贴出来。

3. Longest Substring Without Repeating Characters

题目：给一个长字符串s寻找最长的子字符串，该字符串内没有重复的字符。
思路：遍历长字符串，当字符在子字符串出现，首先比较原子字符串是否是目前最长子字符串，如果是将长度存在count中；然后，找到子字符串重复字符位置，该位置的下一个位置就是新子字符串开始的位置。
注意：
（1）str.find(ch)的使用，返回第一个匹配位置，否则返回。
（2）循环结束需要再次算长度，初学者容易忘记。

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字符串后加了一个空格' '。目的是人工创建了一个边界而不影响原字符串的特征，这样我就可以不用检测右侧边界了。

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"，我们要写一个函数，函数的功能如下：

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

思路：这个题目主要就是找到回形针模式下字符串的规律，将给的字符串进行三部分处理：第一行，中间数行，最后一行。原因很简单，只有中间数行在一次回形针模式输出中输出两次。数学规律并不难找，参考代码即可。
注意：
（1）T是一个循环周期有多少字符数，row是处理回形针模式内的所在行，offset是字符所在位置。
（2）中间行也可能输出一次，出现这种情况只能是在最后一个不完整的周期内。

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

题目：将整型数字转化为罗马数字（字符串）。
思路：暴力蛤希表，罗马数字的规则请自行百度谷歌。暴力代码如下（码的挺累的）
注意：哈希表中加入0这个元素，可以有效地减少代码量。
补充：/和//的区别。如果除数与被除数都是整型，结果是一样的。问题出在如果除数为浮点数，那么结果虽然同为浮点数，但/的结果是向下取整，而//的结果是四舍五入。

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

题目：将罗马数字（字符串）转化为整型数字。
思路：当罗马数字5，50，500左侧出现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

题目：寻找字符串数组中最长的公共前缀
思路：遍历数组即可。

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

题目： 给一个数字字符串，返回所有可能的字符串组合（数字与字符的映射关系参照手机）
思路：建立一个哈希表，用以表示数字和字母间的映射关系。主体是两个循环，第一个循环的给定字符串中的数字，第二个循环是相应数字的不同字符。
注意：拷贝方式，这里我们用result = tmp[:]用以表示result拷贝tmp内的所有内容，而不是两个变量都指向同一个数组地址，否则改变任何一个变量，数组的改变都是联动的。

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

题目：给一个字符串只包含'(', ')', '{', '}', '[' 和 ']'，问字符串是否符合闭合规则。
思路：标准栈的题目，只要处理好进栈和出栈的顺序即可。
注意：如何数组为空，调用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

题目：给一个整数n，按照下面规律找第n个序列。

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

思路：以“1”开始循环n-1次，用count变量计数，遇到前后不相等的情况就更新数据，从而得到最后序列。
注意：在result后面加0，0不可能与之前的数字相等，所以当循环的下一个为0时，一定会调用else里面的内容，这样可以减少代码量。

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区大神的解法，所以在这里注明下，代码十分简洁。其实主要就是几次基于原有列表的排序。sorted(strs, key=sorted)根据列表中每一个自排序后的字符串进行排序，比如：

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

itertools.groupby(list, sorted)的意思是按照排序进行分组，所以比如说"abb","bab"就是存在同一个二级列表中。sorted(members)的意义是对二级列表内元素进行排序。代码如下：

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

题目：找一个字符串中的最后一个单词的长度。
思路：先把两端的空格删去，然后从最后一个字符开始统计，遇到空格就跳出循环，返回正确值。

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

题目：两个二进制数相加。
思路：python玩家不要多想，直接调用函数就好。
注意：bin转换后，得到的是字符串，格式："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()；"."代表着无操作。最后再将结果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

给一个数字，问有多少种解读方式。
思路：主体思路是动态规划。然后就是对情况的总结，顺次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

题目：给一个只包含数字的字符串。将其不同的IP组合存入一个列表中。

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

思路：标准的动态规划+回溯法。当连续顺次的4个数字字符串能够组合且不多余数字的时候，就是一个合格的子答案。所有的答案都储存在列表中。
注意：不能有以0为开头的数字。

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

未完待续