正则表达式匹配
class Solution {
public boolean isMatch(String s, String p){
StringBuilder sb = new StringBuilder();
char[] cs = p.toCharArray();
for(int i = 0; i < cs.length; i++){
while(i < cs.length - 1 && cs[i + 1] == '*' && cs[i] == '*'){
i++;
}
sb.append(cs[i]);
}
p = sb.toString();
char[] sChars = ( " " + s ).toCharArray();
char[] pChars = ( " " + p ).toCharArray();
int sLen = s.length(), pLen = p.length();
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
dp[0][0] = true;
//当匹配串为*时, 要对dp[0][j]进行特殊处理下
for(int j = 2; j <= pLen; j++){
if(pChars[j] == '*') dp[0][j] = dp[0][j - 2];
}
for(int i = 1; i <= sLen; i++){
for(int j = 1; j <= pLen; j++){
if(pChars[j] == '*'){
if(j > 1) dp[i][j] = dp[i][j - 2];
char c = pChars[j - 1];
for(int k = i; k >= 1; k--){
if(sChars[k] != c && c != '.') break;
dp[i][j] |= dp[k][j - 1];
}
}else {
if(sChars[i] == pChars[j] || pChars[j] == '.'){
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[sLen][pLen];
}
}
最长有效括号
public int longestValidParentheses(String s){
int n = s.length();
char[] a = (" " + s).toCharArray();
int[] dp = new int[n + 1];
int max = 0;
for(int i = 1; i <= n; i++){
if(a[i] == ')'){
if(a[i - 1] == '('){
dp[i] = dp[i - 2] + 2;
}else if(a[i - 1] == ')'){
int miniro = i - dp[i - 1] - 1;
dp[i] = a[miniro] == '(' ? dp[miniro - 1] + dp[i - 1] + 2 : 0;
}
}
max = Math.max(dp[i], max);
}
return max;
}
版权声明:本文为weianluo原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。