首页 > 代码库 > [LeetCode]Distinct Subsequences 匹配(不要求连续)的子串
[LeetCode]Distinct Subsequences 匹配(不要求连续)的子串
一开始第一反映是用暴搜+回溯剪枝,妥妥的超时,见numDistinct0函数。
后来想到这跟公共子串有点类似,满足最优子结构和重叠问题,因此可用DP。
状态转移方程如下:
{ dp[i-1,j-1]+dp[i-1][j] , 当s[i]==s[j],0<i<s.size(),0<j<t.size(),
dp[i,j]={ dp[i-1][j], 当s[i]!=s[j] ,0<i<s.size(),0<j<t.size(),
{ 0, i<j(保证t中前j个都匹配到), s.size()-i>t.size()-j(保证s后续元素数够匹配)
初始条件:dp[i][1]=1 if s[i]==t[0]
复杂度O(nm)
class Solution { public: int cnt,n,m; int *num; void count(string &s,int ids,string &t,int idt){ if(idt>=m){ cnt++; return; } if(m-ids<n-idt||num[t[idt]]<=0)return; if(s[ids]==t[idt]){ num[s[ids]]--; count(s,ids+1,t,idt+1); num[s[ids]]++; } num[s[ids]]--; count(s,ids+1,t,idt); num[s[ids]]++; } int numDistinct0(string s, string t) { n=s.size(); m=t.size(); cnt=0; num=new int[256]; memset(num,0,sizeof(int)*256); for(int i=0;i<n;++i)num[s[i]]++; count(s,0,t,0); return cnt; } int numDistinct (string s, string t) { n=s.size(); m=t.size(); int i,j,**d=new int*[n+1]; for(i=0;i<=n;++i){ d[i]=new int[m+1]; memset(d[i],0,sizeof(int)*(m+1)); } for(i=0;i<n;++i){ if(s[i]==t[0])d[i+1][1]=1; } for(i=1;i<=n;++i){ for(j=1;j<=i&&j<=m;++j){ if(n-i<m-j)continue; d[i][j]+=d[i-1][j]; if(s[i-1]==t[j-1]) d[i][j]+=d[i-1][j-1]; } } return d[n][m]; } };
[LeetCode]Distinct Subsequences 匹配(不要求连续)的子串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。