首页 > 代码库 > leetcode第一刷_Interleaving String
leetcode第一刷_Interleaving String
有关这种字符串的题真是层出不穷啊,而且他们都有这样一个特点,就是递归的思路如此简单,但一定超时!
这个时候,dp就朝我们缓缓走来。递归超,dp搞!这道题的状态转移方程还是比较好写的,用ispart[i][j]代表s1贡献i长,s2贡献j长时,能不能形成s3的前i+j个字符。更新可以按照行或者列开始,s3的前i+j个字符,可以是((i-1)+1)+j构成,也可以是i+((j-1)+1)构成,这取决于当前的这个字符s3[i+j-1]跟s1[i-1]和s2[j-1]是否相等,或的关系就可以解决问题。
边界条件也很好确定,就是当只有一个string参与构造时的情况,注意一旦有不相等的字符,那么后面的全都白搭。
class Solution { public: bool isInterleave(string s1, string s2, string s3) { int l1 = s1.length(), l2 = s2.length(), l3 = s3.length(); if(l3 != l1+l2) return false; bool ispart[l1+1][l2+1]; memset(ispart, 0, sizeof(ispart)); ispart[0][0] = 1; for(int i=0;i<l1;i++){ if(s1[i] == s3[i]) ispart[i+1][0] = 1; else break; } for(int i=0;i<l2;i++){ if(s2[i] == s3[i]) ispart[0][i+1] = 1; else break; } for(int i=1;i<=l1;i++){ for(int j=1;j<=l2;j++){ ispart[i][j] = (s1[i-1]==s3[i+j-1]&&ispart[i-1][j])||(s2[j-1]==s3[i+j-1]&&ispart[i][j-1]); } } return ispart[l1][l2]; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。