【LeetCode:(每日一题1023. 驼峰式匹配) -＞ 剑指 Offer II 097. 子序列的数目 | 暴力递归=＞记忆化搜索=＞动态规划】

🍎作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🍎座右铭：人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯🎯

题目链接

• 剑指 Offer II 097. 子序列的数目
• 115. 不同的子序列

题目描述

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 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

提示：

0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

求解思路&实现代码&运行结果

暴力递归

求解思路

1. 接下来我给大家分析一下我对整个题目的思考过程：
2. 首先，我想到的解决方案是从字符串s的0位置开始，到最后一个位置结束，找到s的子序列在t出现的个数。那么这个过程开上去好像没有什么问题，但是仔细一研究就会发现整个过程和t脱离了联系，而且无从下手，所以我们直接pass掉。
3. 其次想到的解决方案就是我们需要去比较此时s的某一个位置和t的某一个位置是否相等，所以我就想到了设置俩个指针，一个指向s的位置，一个指向t的位置，如果此时这俩个位置相同，有以下俩种的方案，1.我们可以继续向后进行判断，俩个指针同时向后移动，继续判断； 2.指向s的指针向后移动，可以和原来指向t的指针继续判断；然后就是如果此时这俩个位置是不相等的，那么和我们上面2的操作是一样的，继续判断即可。

实现代码

class Solution {public int numDistinct(String s, String t) {int m=s.length(),n=t.length();char[] arr1=s.toCharArray();char[] arr2=t.toCharArray();return process(0,arr1,0,arr2);}public int process(int index1,char[] arr1,int index2,char[] arr2){if(arr2.length-index2>arr1.length-index1) return 0;if(index2==arr2.length){return 1;}if(index1==arr1.length) return 0;if(arr1[index1]==arr2[index2]){return process(index1+1,arr1,index2+1,arr2)+process(index1+1,arr1,index2,arr2);}else{return process(index1+1,arr1,index2,arr2);}}
}

运行结果

记忆化搜索

求解思路

1. 根据我们递归的分析，在递归的过程中会产生重复的子过程，所以我们想到了加一个缓存表，也就是我们的记忆化搜索。

实现代码

class Solution {public int numDistinct(String s, String t) {int m=s.length(),n=t.length();int[][] dp=new int[m][n];char[] arr1=s.toCharArray();char[] arr2=t.toCharArray();for(int i=0;i<m;i++) Arrays.fill(dp[i],-1);return process(0,arr1,0,arr2,dp);}public int process(int index1,char[] arr1,int index2,char[] arr2,int[][] dp){if(arr2.length-index2>arr1.length-index1) return 0;if(index2==arr2.length){return 1;}if(index1==arr1.length) return 0;if(dp[index1][index2]!=-1) return dp[index1][index2];if(arr1[index1]==arr2[index2]){return dp[index1][index2]=process(index1+1,arr1,index2+1,arr2,dp)+process(index1+1,arr1,index2,arr2,dp);}else{return dp[index1][index2]=process(index1+1,arr1,index2,arr2,dp);}}
}

运行结果

动态规划

求解思路

1. 接下来我们根据之前的递归思路以及记忆化缓存改写动态规划。

实现代码

class Solution {public int numDistinct(String s, String t) {int m=s.length(),n=t.length();int[][] dp=new int[m+1][n+1];char[] arr1=s.toCharArray();char[] arr2=t.toCharArray();for(int i=0;i<=m;i++) dp[i][n]=1;for(int index1=m-1;index1>=0;index1--){for(int index2=n-1;index2>=0;index2--){if(arr1[index1]==arr2[index2]){dp[index1][index2]=dp[index1+1][index2+1]+dp[index1+1][index2];}else{dp[index1][index2]=dp[index1+1][index2];}}}return dp[0][0];}
}

运行结果

课后练习(LeetCode每日一题)

题目链接

• 1023. 驼峰式匹配

题目描述

如果我们可以将小写字母插入模式串 pattern 得到待查询项 query，那么待查询项与给定模式串匹配。（我们可以在任何位置插入每个字符，也可以插入 0 个字符。）

给定待查询列表 queries，和模式串 pattern，返回由布尔值组成的答案列表 answer。只有在待查项 queries[i] 与模式串 pattern 匹配时， answer[i] 才为 true，否则为 false。

求解思路

1. 思路1：和我们上面题目的思路一样(展示)。
2. 思路2：双指针(自行实现)。

实现代码

class Solution {public List<Boolean> camelMatch(String[] queries, String pattern) {List<Boolean> ans=new ArrayList<>();for(int i=0;i<queries.length;i++){ans.add(process(0,queries[i],0,pattern));}return ans;}public boolean process(int i,String queries,int j,String pattern){// 如果此时j指针到达了pattern字符串的结尾位置if(j==pattern.length()){// 我们判断一下queries字符串中是否还有大写字母 如果有的话，直接返回falsewhile(i<queries.length()){if(Character.isUpperCase(queries.charAt(i))) return false;i++;}// 如果遍历完成后，没有返回false 那就是true了return true;}// 如果j指针没有达到结束位置，但是此时i指针到达结束位置了，直接返回falseif(i==queries.length()) return false;// 如果此时queries的某个位置的字符是大写的话if(Character.isUpperCase(queries.charAt(i))){// 我们需要判断此时俩个字符串是否匹配，如果匹配 直接递归下一个位置 否则 直接falseif(queries.charAt(i)==pattern.charAt(j)) return process(i+1,queries,j+1,pattern);else return false;}else{// 如果当前queries某个位置是小写的话，那么我们继续判断// 此时字符串中俩个位置的值是否相等，如果相等，我们可以有多种选择// 1.i和j指针同时移动到下一个位置 2.queries的i指针继续向后移动if(queries.charAt(i)==pattern.charAt(j)){return process(i+1,queries,j+1,pattern)|| process(i+1,queries,j,pattern);}else{// 如果不想等，queries的i指针继续向后移动和j指针匹配return process(i+1,queries,j,pattern);}}}
}

• 说明: 几乎所有的字符串匹配问题都是可以使用动态规划求解的.

共勉

最后，我想送给大家一句一直激励我的座右铭，希望可以与大家共勉！