交错字符串 Interleaving String

发布时间:2016-12-6 18:15:02 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"交错字符串 Interleaving String",主要涉及到交错字符串 Interleaving String方面的内容,对于交错字符串 Interleaving String感兴趣的同学可以参考一下。

判断字符串c是否是字符串a和字符串b按顺序的交错(interleave)。 什么叫interleave?是将两个字符串完整的交错在一起,拆分开以后还会是原来的a和b串。 一个直观的错觉:把C字符串中的A挑出来,剩下的部分如果是B,这样就说明C是interleave。 这样会遇到一个错误,比如a="aa", b="ab", c="aaba"。如果从c中把A挑出来,会直接挑出开始的"aa",然后剩余的部分"ba"不等于b字符串,就会做出“不是interleave”的错误判断。这样的错误是由于a、b两个字符串中有共有的字符所导致的挑拣时的错误。 情况一:如果输入字符串a、b中没有共有的字符,那么各挑各的,挑到就一定是属于自己的。如果挑完之后c还有剩余、或者挑不完c就没了,说明c不是interleave。 情况二:如果输入字符串a、b中是有共有字符的,那么各挑各的,很有可能发生挑选错误,把不该挑走的挑走。想要避免这个错误,当遇到共有字符时(即,两方都能要的字符),分别把两种情况都考虑。 下面是解决问题的两种方向。 1、递归方法:由外向里(由大向小)解决问题。 2、DP方法:由里向外(由小向大)解决问题。 递归子问题方法: 对于目标问题(s1, s2, s3)来说,递归子问题是(s1.substr(1), s2, s3.substr(1))和(s1, s2.substr(1), s3.substr(1))两个。 class Solution { public: bool isInterleave(string s1, string s2, string s3) { bool r1 = false, r2 = false; if(s1 == "" && s2 == "" && s3 == "") return true; if(s1 != "" && s3 != "" && s1[0] == s3[0]) r1 = isInterleave(s1.substr(1), s2, s3.substr(1)); if(s2 != "" && s3 != "" && s2[0] == s3[0]) r2 = isInterleave(s1, s2.substr(1), s3.substr(1)); return r1 || r2; } }; 动态规划方法: 国际惯例,首先找子问题,设计子问题状态量。 对于目标问题(s1, s2, s3)来说,子问题是(s1的前i个字符,s2的前j个字符,s3的前i+j个字符)。 设子问题状态量C[i][j],其表示,问题(s1的前i个字符,s2的前j个字符,s3的前i+j个字符)的状态(true或false)。那么C[s1.length()][s2.length()]就是目标问题的状态。 初始问题状态C[0][0]=true。 状态递推关系为: C[i][j] = ( (s1[i-1] == s3[i+j-1]) && C[i-1][j] ) || ( (s2[j-1] == s3[i+j-1]) && C[i][j-1] ) 代码: class Solution { public: bool isInterleave(string s1, string s2, string s3) { size_t len1, len2; len1 = s1.length(); len2 = s2.length(); if(len1 + len2 != s3.length()) return false; bool **C = new bool*[len1+1]; //注意*在中间 for(int i=0;i<len1+1;i++) C[i] = new bool[len2+1]; C[0][0] = true; for(int i=1;i<len1+1;i++) C[i][0] = (s1[i-1] == s3[i-1]) && C[i-1][0]; for(int j=1;j<len2+1;j++) C[0][j] = (s2[j-1] == s3[j-1]) && C[0][j-1]; for(int i=1;i<len1+1;i++) for(int j=1;j<len2+1;j++) C[i][j] = ( (s1[i-1] == s3[i+j-1]) && C[i-1][j] ) || ( (s2[j-1] == s3[i+j-1]) && C[i][j-1] ); bool result = C[len1][len2]; for(int i=0;i<len1+1;i++) delete []C[i]; delete []C; return result; } }; DP方法的时间复杂度O(mn),空间复杂度O(mn)。

上一篇:黑马程序员 while语句
下一篇:手机重力感应控制电脑(二)

相关文章

相关评论