字符串问题

1.找一个字符串中无重复的连续最长子串，返回长度。Longest Substring Without Repeating Characters

思路：使用hashmap<char，int>保存每个字符及其位置，ij两个指针指向子串的起止位置,i从左到右循环，j是用于标记子字符串最左的位置。先判断当前字符是否在map中有，如果在，那么更新j的位置为map中i的位置的下一个位置map.get(s.charAt(i) +1)或之前j中的最大值;每次循环中加入一个字符，并更新最大长度。

2.求一个字符串数组的最长前缀公共子串

https://leetcode.com/problems/longest-common-prefix/description/

思路：初始子串为数组第一个字符串的值。用两个while（）嵌套循环。外循环是字符串数组的个数；内循环是，子串在当前字符串中的起始位置是否为0，若不为0，则从尾部去掉子串的一个字符。

3.回文串问题

回文串：“aba”  “ttaatt”

（1）判断一个字符类型的字符串是否为回文串

https://leetcode.com/problems/valid-palindrome/description/

思路：使用两个指针head，tail分别指向字符串的头和尾，对s[head] == s[tail] 进行判断，若为真，则head++；tail--；否则返回false。直到head不再小于等于tail为止。

本题稍微复杂一点，需要额外对字符串进行去标点和空格处理，使用正则表达式处理。

（2）判断一个数字类型的字符串是否为回文串

思路:不用额外的空间，这里使用两个int变量x，y。

（3）求一个字符串中的最长回文串及其长度

思路：使用两个指针i,j分别标记子串的起止位置，再用dp【i】【j】数组表示当前ij字符串是否为回文。dp[i][j] = (s[i] == s[j] && (j - i < 3 ||dp[i+1][j-1]));

若是回文，那么子串就是i，j所在的字符串。最好输出子串（或子串长度）

（4）求一个字符串中的所有回文串的个数

思路：使用上面一题相同的思路，只是在判断dp【】【】为真时，计数器加一。

4.字符串中的括号问题

括号字符串匹配问题一般考虑利用“栈”的先进后出特性实现。

（1）判断一个字符串是否为匹配的括号字符串。这里包括（）【】{}六种字符。

使用一个栈，将每个字符进行入站出站操作。当前字符为‘（’时，入栈；

当前字符为‘）’，先判断栈是否为空，若空，则返回false；

                                                                若不空，检查是否为一对括号，是，出栈，不是，返回false。

（2）求长度为N的所有匹配的括号字符串。这里只有（）两种字符。

思路：使用递归的思想，以及两个int分别存储还剩的左括号个数、右括号个数。

（3）求最长的匹配的括号字符串。这里只有（）两种字符

待更新。。。

5.求一个字符串的连续最大递增子串的长度

思路：使用一个string保存最长的子串，使用一个指针i，从左向右遍历。当s[i] < s[i - 1],更新子串为s[i],最长长度为1；

当s[i] >= s[i - 1],子串尾部加入s[i]。

6.求两个字符串的最长公共子串的长度（或字符串）

如：s1 = "thisgood" s2 = "sgo"

公共子串为“sgo”，长度为3。

思路：使用游标的思想。将两个字符串看做两个尺子，把尺子从头到尾对齐扫描一遍。

可以看出，例子中最长的子串长度为3。

代码如下。

求最长字符串的代码如下。