记一次LeetCode解题（087-扰乱字符串）

2020-01-28 08:00

背景

最近几个月，每周坚持做力扣（LeetCode）的算法题。计算机编程果然是熟能生巧的技能，目前我已经完成了八十多道力扣算法题，明显感觉到自己算法编写的能力又提升了。

今天这一篇，打算对刚完成的一道算法题做下记录，顺便写写自己的一些简单心得体会。这是力扣第87题《扰乱字符串》，其难度级别是“困难”，我也的确花了些时间，才最终完成解题，不过最终成绩还不错：

执行用时4 ms，排名超过97.87%的C++提交者。
内存消耗8.4MB，排名超过95.70%的C++提交者。

解题尝试的具体代码（包含中间版本和最终版本）详见于：https://github.com/yanlinlin82/leetcode/blob/master/00087_scramble-string/

题目描述

原题是这样的（转载自力扣网站）：

给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。

下图是字符串 s1 = “great” 的一种可能的表示形式。
        great
       /    \
      gr    eat
     / \    /  \
    g   r  e   at
               / \
              a   t
在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。

例如，如果我们挑选非叶节点 “gr” ，交换它的两个子节点，将会产生扰乱字符串 “rgeat” 。
        rgeat
       /    \
      rg    eat
     / \    /  \
    r   g  e   at
               / \
              a   t
我们将 “rgeat” 称作 “great” 的一个扰乱字符串。

同样地，如果我们继续交换节点 “eat” 和 “at” 的子节点，将会产生另一个新的扰乱字符串 “rgtae” 。
        rgtae
       /    \
      rg    tae
     / \    /  \
    r   g  ta  e
           / \
          t   a
我们将 “rgtae” 称作 “great” 的一个扰乱字符串。

给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。

示例 1:
输入: s1 = "great", s2 = "rgeat"
输出: true
示例 2:
输入: s1 = "abcde", s2 = "caebd"
输出: false

我的解题过程

第一次尝试

代码链接：200128-1.cpp

解算法题，首先第一步，是正确理解题意。正确理解题意后，才能思考如何使用算法实现该过程，进而解决问题。

对于这道题，最直接的做法，是按照题意的示例说明，也构造相应的二叉树。然而，二叉树的构建，尤其是枚举所有可能的不同分叉节点，会是非常耗时的做法，所以，应考虑等价效果的其他高效方法。
于是，一个直接的思路是，从已经排序好的数组中，挑选一个元素，元素左边的所有元素都比该元素小，而元素右边的所有元素都比该元素大，则认为合法，否则非法。再考虑到原题设定允许二叉树的任意节点做左右交换，于是考虑这样的判断条件：“左边都小”且“右边都大”，或者“左边都大”且“右边都小”。
由于二叉树的左枝和右枝，都分别是一个二叉树，于是将上述判断递归地应用于左右两个子枝，即可完成题目所需的最终判断。
此外，由于输入的是字符串，要判断“都大”或“都小”，就需要把字符串转换成为整数数组，数组元素用字符所在的位置表示即可。

上述思路，就形成了这第一次尝试的代码。

代码简单说明如下：

主函数bool Solution::isScramble(string s1, string s2)中，使用了unordered_map帮助，首先将字符映射成为表示位置的整数字符串：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


bool isScramble(string s1, string s2) {
    unordered_map<char, int> index;
    for (int i = 0; i < s1.size(); ++i) {
        index[s1[i]] = i;
    }
    vector<int> a;
    for (int i = 0; i < s2.size(); ++i) {
        a.push_back(index[s2[i]]);
    }
    return isScramble(a, 0, a.size() - 1);
}

主函数中调用了一个重载的执行函数bool Solution::isScramble(const vector<int>& a, int i, int j)，用以实现递归判断，参数中给出了判断的数组范围边界（i和j分别表示左边界和右边界），使不需要每次都做繁琐耗时的数组拷贝：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


bool isScramble(const vector<int>& a, int i, int j) {
    if (j - i < 2) return true;
    for (int k = i + 1; k <= j - 1; ++k) {
        if (isPartition(a, i, j, k)) {
            if (isScramble(a, i, k - 1) && isScramble(a, k + 1, j)) {
                return true;
            }
        }
    }
    return false;
}

在上面的执行函数中，用循环依次尝试不同位置的划分，并使用了一个bool Solution::isPartition(const vector<int>& a, int i, int j, int k)函数，根据左右是否“都大”或“都小”，来确认划分是否正确，不正确的划分，就不需要进一步递归判断子枝了：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


bool isPartition(const vector<int>& a, int i, int j, int k) {
    if (a[i] < a[k] && a[j] < a[k]) return false;
    if (a[i] > a[k] && a[j] > a[k]) return false;
    if (a[i] < a[k]) {
        for (int l = i + 1; l < k; ++l) {
            if (a[l] > a[k]) return false;
        }
        for (int l = k + 1; l < j; ++l) {
            if (a[l] < a[k]) return false;
        }
    } else {
        for (int l = i + 1; l < k; ++l) {
            if (a[l] < a[k]) return false;
        }
        for (int l = k + 1; l < j; ++l) {
            if (a[l] > a[k]) return false;
        }
    }
    return true;
}

整个逻辑看起来不错，提交后，却发现出现“解答错误”。检查发生错误的输入内容，原来是s2字符串中有s1中不存在的字符（s1="a", s2="b"）。

第二次尝试

代码链接：200128-2.cpp

第二次尝试的修改很简单，真丢上面遇到的问题，在构造位置数组时，判断一下是否存在即可。如下代码所示，新增的第8行代码，就是判断s2中若存在新字符，则直接返回false：

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


bool isScramble(string s1, string s2) {
	unordered_map<char, int> index;
	for (int i = 0; i < s1.size(); ++i) {
		index[s1[i]] = i;
	}
	vector<int> a;
	for (int i = 0; i < s2.size(); ++i) {
		if (index.find(s2[i]) == index.end()) return false;
		a.push_back(index[s2[i]]);
	}
	return isScramble(a, 0, a.size() - 1);
}

然而，这次提交也失败了，“解答错误”的输入内容是：s1="ab", s2="aa"。也就是说，s2中存在重复字符。的确，s2中的所有字符在s1中都出现过了，但因为重复字符，并没有对s1覆盖全呢。

第三次尝试

代码链接：200128-3.cpp

所以，接下来，自然是把s1与s2的字符是否一一对应的判断，做得更完备了。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


bool isScramble(string s1, string s2) {
	unordered_map<char, int> index;
	for (int i = 0; i < s1.size(); ++i) {
		index[s1[i]] = i;
	}
	vector<int> a;
	unordered_map<char, int> flag;
	for (int i = 0; i < s2.size(); ++i) {
		if (index.find(s2[i]) == index.end()) return false;
		if (flag.find(s2[i]) != flag.end()) return false;
		a.push_back(index[s2[i]]);
		flag[s2[i]] = 1;
	}
	return isScramble(a, 0, a.size() - 1);
}

然而，这次提交还是失败了，“解答错误”的输入内容是：s1="aa", s2="aa"。也就是说，s1中存在重复字符，于是，把字符映射成单一位置整数的做法，似乎就行不通了。

第四次尝试

代码链接：200128-4.cpp

既然“把字符映射成表示位置的整数”这条思路行不通，那么就还是考虑直接用原字符串做“二叉树节点翻转”的尝试吧。把“左右两侧的某侧，是否都大或都小”判断，改成“翻转后的字符，是否与翻转前的字符，集合上完全一致”。

在进行这个尝试前，还注意到之前的一个误解，认为需要先找到一个“相等的中间节点”，然后分别判断其“左侧”和“右侧”。然而，从题目示例给出的二叉树看，其实划分并不是发生在某个元素上，而是发生在两个元素之间的间隔上。

顺着这个思路，就有了第四次尝试的代码，使用单一函数递归即可完成判断，代码也简化了许多：

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


bool isScramble(string s1, string s2) {
	int n = s1.size(), n2 = s2.size();
	if (n != n2) return false;
	if (n == 1) return (s1 == s2);
	for (int i = 1; i < n; ++i) {
		if (isScramble(s1.substr(0, i), s2.substr(0, i)) &&
				isScramble(s1.substr(i), s2.substr(i))) {
			return true;
		}
		if (isScramble(s1.substr(0, i), s2.substr(n - i)) &&
				isScramble(s1.substr(i), s2.substr(0, n - i))) {
			return true;
		}
	}
	return false;
}

然而，这次提交依然失败，报出了“超出时间限制”的错误。对于失败的输入，字符串本身并不长（s1="ccabcbabcbabbbbcbb", s2="bbbbabccccbbbabcba"），在本地测试，的确结果并不能秒回。看来，接下去需要进一步优化代码运行速度了。

第五次尝试

代码链接：200128-5.cpp

优化代码速度，考虑几个方面：

在递归过程中，使用了字符串处理函数substr，重新构造了新字符串，这个过程的确很耗时，考虑使用指针和字符串长度来替代，这样整个程序中，只需要保留原字符串一个拷贝即可。
对于字符串长度只有1或2的情况，若能保证字符集合相同，则肯定是能满足“二叉树翻转能得到”的，可以直接返回true，简化运算。
对于是否进行分支的递归判断，应该首先判断字符集合是否相同。
字符集合相同，考虑到字符取值一定是0~255（按照无符号计算），于是直接使用一个固定大小的局部数组（256长度），在s1中累加，在s2中递减，预期刚好每个字符的计数应该都减为0，若有减为负数的，说明字符集合不相同。

基于上述策略，得到最终的成功代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


bool isScramble(string s1, string s2) {
    int n = s1.size(), n2 = s2.size(); if (n != n2) return false;
    return isScramble(s1.c_str(), s2.c_str(), n);
}
bool isScramble(const char* s1, const char* s2, int n) {
    if (n==1) return *s1 == *s2;
    if (n==2) return (*s1 == *s2 && *(s1+1) == *(s2+1)) || (*s1 == *(s2+1) && *(s1+1) == *s2);
    if (!isLetterTheSame(s1, s2, n)) return false;
    for (int i = 1; i < n; ++i) {
        if (isScramble(s1, s2, i) && isScramble(s1 + i, s2 + i, n - i)) return true;
        if (isScramble(s1, s2 + (n - i), i) && isScramble(s1 + i, s2, n - i)) return true;
    }
    return false;
}
bool isLetterTheSame(const char* s1, const char* s2, int n) {
    int c[256] = { 0 };
    for (int i = 0; i < n; ++i) { ++c[(unsigned int)s1[i]]; }
    for (int i = 0; i < n; ++i) { if (--c[(unsigned int)s2[i]] < 0) return false; }
    return true;
}

心得小结

算法实现，不太容易一步到位，经常有边界条件容易被忽略，需要在后期测试过程中，充分发散考虑，并逐个进行修补。
对于一些基本题意，尽量不要想当然（比如假定没有重复字符等），因为这可能导致某些行不通的错误思路上浪费时间。
相比使用原生C语言，C++提供了诸如vector、list、set/unordered_set、map/unordered_map等基础常用数据结构，方便了各类算法实现。
避免数组、字符串的大量拷贝，是提高运行速度的关键。
递归函数是利器，通过函数参数，区分出问题的简化情况和复杂情况，对简化情况直接处理，对复杂情况则用简单情况进行构建，在代码实现上会很方便，也很有效，这有点像数学证明中的归纳法。

颜林林的个人网站

Linlin Yan's Personal Website