leetcode 字符串动态规划总结
问题1:leetcode 正则表达式匹配
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配
思路:
如果 pattern[j] == str[i] || pattern[j] == '.', 此时dp[i][j] = dp[i-1][j-1];
此时dp[i][j] = dp[i][j-2] //a*匹配0次
public boolean match(char[] str, char[] pattern)
{
if(str == null || pattern == null) return true;boolean [][] dp = new boolean[str.length+1][pattern.length+1];
dp[0][0] = true;
for(int i=1; i<dp[0].length;i++){
if(pattern[i-1] == '*'){
dp[0][i] = dp[0][i-2];
}
}
for(int i=1; i<dp.length; i++){
for(int j=1;j<dp[0].length; j++){
if(pattern[j-1] == '*'){
if(str[i-1] == pattern[j-2] || pattern[j-2] == '.'){
dp[i][j] = dp[i][j-2] || dp[i-1][j] || dp[i][j-1];
// 0 多次 一次
}
else{
dp[i][j] = dp[i][j-2];
}
}
else if(str[i-1] == pattern[j-1] || pattern[j-1] == '.'){
dp[i][j] = dp[i-1][j-1];
}
}
} for(int i=0; i<dp.length; i++){
for(int j=0; j<dp[0].length; j++){
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
return dp[dp.length-1][dp[0].length-1];
}
问题2: leetcode 44 通配符匹配
给定一个字符串 (s
) 和一个字符模式 (p
) ,实现一个支持 '?'
和 '*'
的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。
两个字符串完全匹配才算匹配成功。
思路: 定义dp[i][j]为s的前i个字符与p的前j个字符是否匹配,那么当p[j] 为‘*’的时候, dp[i][j] = dp[i][j-1] || (i >0 && (dp[i-1][j] || dp[i-1][j-1]) );// 匹配多次或者一次
当p[j-1]为“?”时候,dp[i][j] = dp[i-1][j-1]
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n=p.length();
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
// String str = "adceb";
// String pattern = "*a*b";
for(int i = 0; i<=m; i++){
for(int j=1;j<=n;j++){
if( p.charAt(j-1)=='*'){
dp[i][j] = dp[i][j-1] || (i >0 && (dp[i-1][j] || dp[i-1][j-1]) );// 匹配多次或者一次
}
if( i>=1 && (p.charAt(j-1)=='?' || s.charAt(i-1) == p.charAt(j-1)) ){
dp[i][j] = dp[i-1][j-1];
}
}
} // for(int i = 0; i<=m; i++){
// for(int j=0;j<=n;j++) {
// System.out.print(dp[i][j] + " ");
// }
// System.out.println();
// }
return dp[m][n];
}
}
问题三:leetcode 97 交替字符串
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false 思路: 定义dp[i][j]为s1的前i个字符与s2的前j个字符是否可以组成s3的前i+j个字符,注意空字符串,所以s1与s2都是从1开始计数的
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.equals("")){
return s2.equals(s3);
}
if(s2.equals("")){
return s1.equals(s3);
} int m = s1.length(), n = s2.length();
if(m+n != s3.length()){
return false;
}
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true; // String s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"; for(int i=0; i<= m; i++){
for(int j=0; j<=n;j++){
if(i==0 && j==0) continue;
dp[i][j] = (i>0 && s1.charAt(i-1)==s3.charAt(i+j-1) && dp[i-1][j]) ||
(j>0 && s2.charAt(j-1) == s3.charAt(i+j-1) && dp[i][j-1] );
}
} // for(int i=0; i<= m; i++){
// for(int j=0; j<=n;j++) {
// System.out.print(dp[i][j] +" ");
// }
// System.out.println();
// }
return dp[m][n];
}
}
leetcode 不同子序列 115
给定一个字符串 S 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE"
是 "ABCDE"
的一个子序列,而 "AEC"
不是)
示例 1:
输入: S ="rabbbit"
, T ="rabbit"
解释:
输出: 3
如下图所示, 有 3 种可以从 S 中得到"rabbit" 的方案
。
(上箭头符号 ^ 表示选取的字母)rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
示例 2:
输入: S ="babgbag"
, T ="bag"
解释:
输出: 5
如下图所示, 有 5 种可以从 S 中得到"bag" 的方案
。
(上箭头符号 ^ 表示选取的字母)babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
思路1: 定义 dp[i][j] 为s[i]等于t[j]的子序列数目:dp[i][j] += dp[k][j-1]; s[k] = t[j-1];
class Solution {
public int numDistinct(String s, String t) {
// S = "rabbbit", T = "rabbit" // String S = "babgbag", T = "bag";
int m = s.length(), n = t.length();
int[][] dp = new int[m][n];
// dp[i][j] = dp[k][j-1] s[k] == t[j]
for(int i=0; i<m;i++){
dp[i][0] = s.charAt(i) == t.charAt(0) ? 1 : 0;
}
for(int i=0; i<m;i++){
for(int j=0; j<n;j++){
if(s.charAt(i) == t.charAt(j)) {
for (int k = 0; k < i; k++) {
if (j>0 && s.charAt(k) == t.charAt(j-1)) {
dp[i][j] += dp[k][j-1];
}
}
}
}
}
// for(int i=0; i<m;i++) {
// for (int j = 0; j < n; j++) {
// System.out.print(dp[i][j]+" ");
// }
// System.out.println();
// }
int result = 0;
for(int i=0 ; i<m;i++){
result += dp[i][n-1];
}
return result;
}
}
思路2:
而是判断S有多少种方式可以得到T。但其实还是动态规划,我们一个定义二维数组dp,dp[i][j]为字符串s(0,i)变换到t(0,j)的变换方法的个数。
如果S[i]==T[j],那么dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。意思是:如果当前S[i]==T[j],那么当前这个字符即可以保留也可以抛弃,所以变换方法等于保留这个字符的变换方法加上不用这个字符的变换方法, dp[i-1][j-1]为保留这个字符时的变换方法个数,dp[i-1][j]表示抛弃这个字符时的变换方法个数。
如果S[i]!=T[i],那么dp[i][j] = dp[i-1][j],意思是如果当前字符不等,那么就只能抛弃当前这个字符。
class Solution {
public int numDistinct(String s, String t) {
int[][] res = new int[s.length()+1][t.length()+1];
res[0][0] = 1;
for(int i=1;i<t.length()+1;i++)
res[0][i] = 0;
for(int i=1;i<s.length()+1;i++)
res[i][0] = 1;
for(int i=1;i<s.length()+1;i++)
for(int j=1;j<t.length()+1;j++){
if(s.charAt(i-1)==t.charAt(j-1)){
res[i][j] = res[i-1][j-1] + res[i-1][j];
}
else{
res[i][j] = res[i-1][j];
}
}
return res[s.length()][t.length()];
}
}
最新文章
- Entity Framework 6 Recipes 2nd Edition(13-5)译 ->; 使POCO的修改追踪更高
- ubuntu 15.10 安装swift开发环境 2016/4/17
- RESTful API测试工具
- 《CMake实践》笔记一:PROJECT/MESSAGE/ADD_EXECUTABLE
- 不安装Oracle客户端使用PLSQL连接Oracle数据库的方法
- 【C语言学习】《C Primer Plus》第5章 运算符、表达式和语句
- Unity 热更新实例一、C#Light 和UI系统使用实例
- Spring mvc 文件上传到文件夹(转载+心得)
- java集合 collection-list-LinkedList 模拟一个堆栈或者队列数据结构。
- js模拟Map对象,实现key---value
- 字符串比较必须使用strcmp
- _.each的用法2
- Struts2拦截器总结
- MouseOver/MouseOut vs MouseEnter/MouseLeave
- Codeforces Round #522 (Div. 2, based on Technocup 2019 Elimination Round 3) D. Barcelonian Distance 几何代数(简单)
- 怎么给easyui中的datagrid加水平滚动条
- Linux-系统编程-知识点概述
- mysql 案例 ~ insert插入慢的场景
- input文字颜色、光标颜色
- 粒子滤波跟踪移动机器人(MATLAB Robotics System Toolbox)
热门文章
- 洛谷 P3865 【模板】ST表
- Jenkins中的Job配置里缺少“触发远程构建(例如,使用脚本)”选项的问题解决
- transition、animation在macbook air上图片动画边缘抖动2
- iOS 内存管理策略
- 使用nginx转发不了静态文件
- springboot mybatis 项目框架源码 shiro 集成代码生成器 ehcache缓存
- [转]JVM堆和栈的区别
- [Testing] JavaScript Mocking Fundamentals
- MySQL和MongoDB的性能测试
- 【转载】Open Live Writer 安装