如果在只由'('和')'两种字符组成的字符串中，每一个符号都有合理的匹配，我们说这个字符串是完整的。
问题1:怎么判断只由'('和')'两种字符组成的字符串是完整的。
问题2:如果一个可能不完整的字符串，怎么求至少需要添加多少个括号能让其完整。
问题3:求只由'('和')'两种字符组成的字符串中，最大完整子串长度。
问题1解法：
用一个变量count, 从左往右遍历字符串，遇到左括号count++，遇到右括号count--，
a.在遍历过程中任何时候如果count<0，说明该字符串不完整，直接返回false，因为遍历字符串的前缀如果发现某个前缀右括号比左括号多，不可能完整，无法匹配。
b.遍历完之后count必须等于0，否则返回false。
以上两种情况的false都没有，返回true。
代码如下：
public static boolean isValid(char[] str) {
if (str == null || str.length == 0) {
return false;
}
int status = 0;
for (int i = 0; i < str.length; i++) {
if (str[i] != ')' && str[i] != '(') {
return false;
}
if (str[i] == ')' && --status < 0) {
return false;
}
if (str[i] == '(') {
status++;
}
}
return status == 0;
}
问题2解法：
用一个变量count, 从左往右遍历字符串，遇到左括号count++，遇到右括号count--，用need统计需要添加的括号数
a.在遍历过程中任何时候一旦发现count==-1，说明单独多出一个右括号，此时需要左括号加在该右括号前面救急，need++。
b.整个遍历完之后，count如果>0，左括号多出count个，说明需要救急的右括号数量就是count，把count累加到need里去。
代码如下：
public static int needParentheses(String str) {
int t = 0;
int needSolveRight = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
t++;
} else { // 遇到的是')'
if (t == 0) {
needSolveRight++;
} else {
t--;
}
}
}
return t + needSolveRight;
}
问题3解法：
首先说明求S标准下的子串、子数组、符合标准的最大累加和（子串子数组是连续的，子序列是不连续的）解题思路：
1.求以每个位置开头的情况下（子串、子数组）在S标准下答案是什么，从右往左，这样就可以复用之前的答案。
2.求以每个位置结尾的情况下（子串、子数组）在S标准下答案是什么，从左往右。
通过已求位置来加速当前位置的求值。
问题3解法为动态规划。开辟元素类型为int且数组大小为字符串长度的dp数组，dp[i]表示如果子串必须以i位置字符结尾，最长有效括号子串长度是多少？
1.i 位置字符是左括号：以左括号结尾，不可能有效，直接dp[i]=0即可；因为任何有效完整的括号字符串都不可能以左括号结尾。
2.i 位置位置是右括号：因为是从左往右求每个位置i的结论，所以有i位置之前（0 ~ i - 1）所有的结论；假如dp[i - 1] = 6，那么往前6个位置，看该位置（(i - 1 - 6)位置，即(i - 7)位置）是不是左括号；如果是左括号，说明(i - 7)位置左括号和 i 位置右括号是一个有效组合，可以把(i - 1)位置结尾的长度为6的有效括号子串给包起来，那么dp[i] = dp[i - 1] + 2 = 6 + 2，如果不是，那么dp[i]=0；如果前面那个位置（(i - 7)位置）不越界，还要在加上那个位置（(i - 7)位置）再前一个位置（(i - 7 - 1)位置）的dp值，因为可以连起来共同构成一个长的子串。
代码如下：
public static int maxLength(String s) {
if (s == null || s.equals("")) {
return 0;
}
char[] str = s.toCharArray();
int[] dp = new int[str.length];
int pre = 0;
int res = 0;
for (int i = 1; i < str.length; i++) {
//如果是左括号，不用讨论，dp值也不用改，默认值0即可
if (str[i] == ')') {
pre = i - dp[i - 1] - 1; // 与str[i]配对的左括号的位置 pre
if (pre >= 0 && str[pre] == '(') {
dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
问题4：给定两个字符串str1和str2，求两个字符串的最长公共子序列（子序列不连续）
这题属于一个样本做行，一个样本做列的动态规划模型。建立二维dp表，行数N为str1长度，列数M为str2长度，dp[ i ][ j ]表示str1从0到i范围的前缀串和str2从0到j范围的前缀串的最长公共子序列有多长，最后所求的即dp[N-1][M-1]。
dp表第一行填法：str1只有一个字符的时候，看与str2有多长的最长公共子序列，遍历str2字符，某个字符与该str1字符相等，那么这一行后面的dp值全为1，因为只有一个字符，后面哪怕匹配了也不可能更长了。第一行逻辑：str2遍历遇到与str1字符相同的字符，dp值填1，然后后面全填1。
dp表第一列同理。
中间普遍位置填法，一共有四种可能性：
第一种可能性，str1从0到i范围的前缀串和str2从0到j范围的前缀串的最长公共子序列不以str1[ i ]结尾也不以str2[ j ]结尾。此时dp[ i ][ j ] = dp[i - 1][j - 1]。
第二种可能性，以str[ i ]结尾，但不以str2[ j ]结尾，dp[ i ][ j ] = dp[ i ][j - 1]。
第三种可能性，不以str1[ i ]结尾，但以str2[ j ]结尾，dp[ i ][ j ] = dp[i - 1][ j ]。
第四种可能性，既以str1[i]结尾，也以str2[j]结尾，注意此时有条件，需要str1[ i ] == str2[ j ]，此时dp[ i ][ j ]= dp[i - 1][j - 1] + 1。
最后这四种情况里取max。
之所以这么分类是因为这么分结果不复杂。按这种可能性分类，普遍位置的值只和邻近几个位置有关，如果不是这么分类可能结果更复杂。
有种优化方式是最后取max时不再是4种情况比较，去掉dp[i - 1][j - 1]的情况。举个例子，假设现在有个普遍位置a，a的左位置记为b，a的上位置记为c，a的左上位置记为d。优化后a位置只依赖b位置和c位置，普遍情况下不再依赖位置d，只有满足条件str1[ i ] == str2[ j ]时才依赖d位置。因为每个位置都依赖自己左边位置和上边位置，求b位置dp值时b位置与d位置是已经比较过的，所以b位置是优于d位置的，但不优于d位置的值再加1。
优化后代码如下：
public static int[][] getdp(char[] str1, char[] str2) {
int[][] dp = new int[str1.length][str2.length];
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
for (int i = 1; i < str1.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);
}
for (int j = 1; j < str2.length; j++) {
dp[0][j] = Math.max(dp[0][j - 1], str1[0] == str2[j] ? 1 : 0);
}
for (int i = 1; i < str1.length; i++) {
for (int j = 1; j < str2.length; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (str1[i] == str2[j]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp;
}
问题5：给定两个字符串str1和str2，求两个字符串的最长公共子串（子串连续）
同样是一个样本做行，一个样本做列的动态规划模型，同样根据结尾列可能性。
dp[ i ][ j ]表示str1从0到i范围的前缀串和str2从0到j范围的前缀串必须既以str1[ i ]结尾，也以str2[ j ]结尾的最长公共子串有多长。与题目5不同的是，这题最后返回的是整张dp表里的最大值。
最终返回的是整张表里的最大值。
dp表第一行填法：str1只有一个字符的时候，看与str2有多长的最长公共子串，遍历str2字符，某个字符与该str1字符相等，那么这个位子的dp值为1，因为必须字符严格相等，所以后面的位置与前面的位置并没有位置依赖。第一行逻辑：str2遍历遇到与str1字符相同的字符，dp值填1，否则填0。
第一列同理。
普遍位置只依赖左上角位置的值。如果str1[ i ] != str2[ j ], dp[ i ][ j ] = 0, 如果如果str1[ i ] == str2[ j ]，dp[ i ][ j ]= dp[ i-1 ][ j-1 ] + 1。
现在稍加修改，不再仅仅是返回长度，而是要返回最长子串，怎么办？
多使用一个变量end记录当前最长子串位置的下标i，每次更新max时同时更新end，最终返回str1的子串（从end位置往前数max个）即可。
返回最长子串的代码如下：
public static String lcst1(String str1, String str2) {
if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
return "";
}
char[] chs1 = str1.toCharArray();
char[] chs2 = str2.toCharArray();
int[][] dp = getdp(chs1, chs2);
int end = 0;
int max = 0;
for (int i = 0; i < chs1.length; i++) {
for (int j = 0; j < chs2.length; j++) {
if (dp[i][j] > max) {
end = i;
max = dp[i][j];
}
}
}
return str1.substring(end - max + 1, end + 1);
}
public static int[][] getdp(char[] str1, char[] str2) {
int[][] dp = new int[str1.length][str2.length];
for (int i = 0; i < str1.length; i++) {
if (str1[i] == str2[0]) {
dp[i][0] = 1;
}
}
for (int j = 1; j < str2.length; j++) {
if (str1[0] == str2[j]) {
dp[0][j] = 1;
}
}
for (int i = 1; i < str1.length; i++) {
for (int j = 1; j < str2.length; j++) {
if (str1[i] == str2[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
}
}
return dp;
}
这题额外空间可以优化到只用几个变量，不使用dp表：
每一轮最开始的出发点从第一行的最右位置往左至（0，0）然后往下到第一列最下位置。每一轮遍历时从出发点往右下角移动到边界，因为普遍位置t只依赖左上角位置的值，所以这种方式必然可以遍历所有公共子串长度，不会遗漏。用一个max保存t的最大值，最后返回t即可。代码如下：
public static String lcst2(String str1, String str2) {
if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
return "";
}
char[] chs1 = str1.toCharArray();
char[] chs2 = str2.toCharArray();
int row = 0; //出发点的行号
int col = chs2.length - 1; //出发点的列号
int max = 0;
int end = 0;
while (row < chs1.length) {
int i = row;
int j = col;
int len = 0;
//向右下方移动这一轮
while (i < chs1.length && j < chs2.length) {
if (chs1[i] != chs2[j]) {
len = 0;
} else {
len++;
}
if (len > max) {
end = i;
max = len;
}
i++;
j++;
}
if (col > 0) {
col--;
} else {
row++;
}
}
return str1.substring(end - max + 1, end + 1);
}
网友评论