google的面试题(三维动态规划的范例)—

转：http://www.cnblogs.com/easonliu/p/3696135.html

分析：
这个问题是google的面试题。由于一个字符串有很多种二叉表示法，貌似很难判断两个字符串是否可以做这样的变换。
对付复杂问题的方法是从简单的特例来思考，从而找出规律。
先考察简单情况：
字符串长度为1：很明显，两个字符串必须完全相同才可以。
字符串长度为2：当s1="ab", s2只有"ab"或者"ba"才可以。
对于任意长度的字符串，我们可以把字符串s1分为a1,b1两个部分，s2分为a2,b2两个部分，满足（(a1~a2) && (b1~b2)）或者（(a1~b2) && (a1~b2)）

如此，我们找到了解决问题的思路。首先我们尝试用递归来写。

解法一（递归）:
两个字符串的相似的必备条件是含有相同的字符集。简单的做法是把两个字符串的字符排序后，然后比较是否相同。
加上这个检查就可以大大的减少递归次数。
代码如下：

注：substr是C++语言函数，主要功能是复制子字符串，要求从指定位置开始，并具有指定的长度。

class Solution {

public:

    bool isScramble(string s1, string s2) {

        int l1 = s1.length();

         int l2 = s2.length();

         if (l1 != l2) return false;

         if (l1 == 1) return s1 == s2;

         string st1 = s1, st2 = s2;

         sort(st1.begin(), st1.end());

         sort(st2.begin(), st2.end());

         for (int i = 0; i < l1; ++i) {

             if (st1[i] != st2[i]) {

                 return false;

             }

         }

         string s11, s12, s21, s22;

         bool res = false;

         for (int i = 1; i < l1 && !res; ++i) {

             s11 = s1.substr(0, i);

             s12 = s1.substr(i, l1 - i);

             s21 = s2.substr(0, i);

             s22 = s2.substr(i, l1 - i);

             res = isScramble(s11, s21) && isScramble(s12, s22);

             if (!res) {

                 s21 = s2.substr(0, l1 - i);

                 s22 = s2.substr(l1 - i, i);

                 res = isScramble(s11, s22) && isScramble(s12, s21);

             }

         }

         return res;

    }

};

解法二（动态规划）：

三维的动态规划还是没有看懂，等哪天静下心来再看看吧·······································

巴特西

google的面试题(三维动态规划的范例)——(87)Scramble String

最新文章

热门文章