leetcode习题分类汇总-String篇



### Generate Parentheses-给N对(),给出所有的组合方式

思路:DFS+backtraceing+具体判断

1. Left代表余下的’(‘的数目

2. right代表余下的’)’的数目

3. 注意right余下的数目要大于left,否则就是非法的,比如,先放一个’)’就是非法的。

4. 任何一个小于0,也是错的。



5. 递归的时候,我们只有2种选择,就是选择’(‘还是选择’)’。

6. 递归的时候,一旦在结果的路径上尝试过’(‘还是选择’)’,都需要回溯,即是sb.deleteCharAt(sb.length() - 1);





### Length of Last Word-返回有空白符的最后一个字符的长度

思路:基本操作,直接用API,split或者s.trim().length()-s.trim().lastIndexOf(“ “)-1




### Valid Parentheses-Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.


思路:用栈的push,pop以及isEmpty()来判断是否符合条件




### Edit Distance-计算从一个单词转换到另一个单词的最小操作数,可以进行替换,插入,删除操作

思路:二维DP:
两个String看成两个char数组,分别是x[m]以及y[n]。对于x[1]…x[i]和y[1]…y[j]的edit distance为A[i][j]。那么有如下recursion:

A[i][j]=A[i-1][j-1] if x[i] = y[j];

A[i][j]=min(A[i-1][j], A[i][j-1], A[i-1][j-1])+1 if x[i] != y[j]

其中第二种x[i]!=y[j]的min中的三个元素分别代表insert, delete和replace三种情况,要看哪种最小。

Base case是A[0][j]=j, A[i][0] = i。

Distinct Subsequences-

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
思路:When you see string problem that is about subsequence or matching, dynamic programming method should come to your mind naturally. The key
is to find the changing condition.

遇到这种两个串的问题,很容易想到DP。但是这道题的递推关系不明显。可以先尝试做一个二维的表int[][] dp,用来记录匹配子序列的个数(以S =”rabbbit”,T = “rabbit”为例):
r a b b b i t
1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
从这个表可以看出,无论T的字符与S的字符是否匹配,dp[i][j] = dp[i][j - 1].就是说,假设S已经匹配了j - 1个字符,得到匹配个数为dp[i][j - 1].现在无论S[j]是不是和T[i]匹配,匹配的个数至少是dp[i][j -
1]。除此之外,当S[j]和T[i]相等时,我们可以让S[j]和T[i]匹配,然后让S[j - 1]和T[i - 1]去匹配。所以递推关系为:
dp[0][0] = 1; // T和S都是空串.
dp[0][1 … S.length() - 1] = 1; // T是空串,S只有一种子序列匹配。
dp[1 … T.length() - 1][0] = 0; // S是空串,T不是空串,S没有子序列匹配。
dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0).1 <= i <= T.length(), 1 <= j <= S.length()



Longest Common Prefix-找到string[]的最大公共前缀


思路:先找到最小字符串,然后两个for循环即可




### Letter Combinations of a Phone Number-给出数字键组合列出所有可能的字母组合。

思路:
先把对应关系存储起来(利用数组下标),然后想办法遍历,DFS或者BFS,可以借助queue




### Count and Say-The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...返回第N个序列

思路:序列的问题首先想到还是DP,根据上一个值求下一个,维护prev的值,然后维护当前元素say和计数count,两个for循环即可。




### Add Binary-二进制数的加法

思路:维护carry和count值,while循环不断insert即可,注意最后一次carry==1需要插入。




### Anagrams-返回string[]中所有回文字符串

思路:
首先简单介绍一下Anagram(回文构词法)。Anagrams是指由颠倒字母顺序组成的单词,比如“dormitory”颠倒字母顺序会变成“dirty room”,“tea”会变成“eat”。

回文构词法有一个特点:单词里的字母的种类和数目没有改变,只是改变了字母的排列顺序。

由此我们可以想到,只要将几个单词按照字母顺序进行排序,就可以通过比较判断他们是否是anagrams。
思路:用map<string, int>记录排序后的字符串以及首次出现的位置。

1. 从strs的第一个元素开始遍历,首先对元素进行排序得到s;

2. 在map里查找s;

3. 若不存在,将s以及该元素的下标存入map<string ,int>;

4. 若存在,首先将第一次出现s时的原始字符串存入结果res,即strs[map[s]],并将map[s]设置为-1(防止下次再存),再将该字符串本身存入结果res;

5. 重复以上1-4步,直到遍历结束。



### Implement strStr()- 判断一个字符串是否是另一个字符串的子串。

思路:这个题目最经典的算法应该是KMP算法,Knuth–Morris–Pratt algorithm。KMP算法是最优的线性算法,复杂度已经达到这个问题的下限。但是KMP算法比较复杂,很难在面试的短时间里面完整正确的实现。所以一般在面试中并不要求实现KMP算法。

采用brute force的算法,假设原串的长度是n,匹配串的长度是m。思路很简单,就是对原串的每一个长度为m的字串都判断是否跟匹配串一致。总共有n-m+1个子串,所以算法时间复杂度为O((n-m+1)m)=O(nm),空间复杂度是O(1)。

Valid Palindrome-判断是否为回文串

思路:把其他符号大小写都去掉然后reverse,判断是否equals即可




### Multiply Strings-字符串相乘,非负数

思路:不能化为数字,要考虑溢出。


方法一:大整数乘法,一位一位往上乘,注意进位的处理即可。此外,注意0的处理
方法二:思路:
1 翻转string
2 建立数组,双层循环遍历两个string,把单位的乘积累加到数组相应的位置
3 处理进位并输出
4 注意前导零的corner case


###

Longest Substring Without Repeating Characters-返回字符串无重复的字符个数

思路:两个指针确定max,用hashmap存储数据




### Longest Palindromic Substring-返回最长的回文子字符串

思路:
思路1:最土的算法,将所有的子串求出来,再选出最长的回文子串。不用试,肯定超时。O(n^3)

思路2:挑出最短的回文串(单个字符,或者两个相邻的相同字符), 然后向两端辐射,时间复杂度O(n^2),空间复杂度可以优化到O(1)

思路3:DP



### Reverse Words in a String-翻转string[]

思路:基本操作,split,stringbuilder优化




### Compare Version Numbers-比较版本大小

思路:基本操作,split后遍历,熟悉三元操作符以及parseInt等API即可。




### String to Integer -字符串转换为数字

思路:基本操作,考虑各种corner case.

1.null or empty string 判断

2.white spaces trim()

3. +/- sign 用flag判断

4.calculate real value double来存储

5.handle min & max


总结:一共40题、只选取了18题,应该说对字符串的操作自己掌握的还是相当糟糕的。主要目的还是掌握字符串的基本操作,至于其他技巧,比如组合排列用DFS+Backtracing,极值问题用DP,存储借助数组或hashmap,反而和string本身的关联不大,多加练习就好。剩余的题目依然还是要找机会补上的。






###