【一天一道LeetCode】#87. Scramble String

一天一道LeetCode

本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处

(一)题目

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = “great”:

great
/
gr eat
/ /
g r e at
/
a t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

rgeat
/
rg eat
/ /
r g e at
/
a t

We say that “rgeat” is a scrambled string of “great”.

Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

rgtae
/
rg tae
/ /
r g ta e
/
t a

We say that “rgtae” is a scrambled string of “great”.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

(二)解题

题目大意:判断两个字符串是不是Scramble String,题目有点长,需要读好久!!!
举个简单的例子说明Scramble String,如ab和ba,那么ab拆分成a和b,ba拆分成b和a,这样就代表为Scramble String。
那么s1和s2是否为Scramble String,就需要将s1和s2拆分成两部分s11和s12,s21和s22,需要判断这两部分是否为Scramble String。
可以分成两个部分:(s11和s21,s12和s22)以及(s11和s22,s12和s21)。
这样一来代码就比较好写了!
很明显的动态规划问题。但是本人在做题过程中的优化还是没有做好,导致超时。

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 != len2) return false;//长度不一样
        if (s1 == s2) return true;//子串相等

        //判断两个子串包含的字符是否相同
        //最开始没加这一步,导致一直超时
        vector<int> count(26,0);
        for(int i = 0 ; i < len1 ; i++)
        {
            count[s1[i]-'a']++;
            count[s2[i]-'a']--;
        }
        for(int i = 0 ; i < 26 ; i++)
        {
            if(count[i]!=0) return false;
        }
        //递归
        for (int i = 1; i < len1; i++)
        {
            string subs1_1 = s1.substr(0, i);
            string subs1_2 = s1.substr(i);
            string subs2_1 = s2.substr(0, i);
            string subs2_2 = s2.substr(i);
            bool is1 = (subs1_1==subs2_1?true:isScramble(subs1_1, subs2_1)) && (subs1_2==subs2_2?true:isScramble(subs1_2, subs2_2));//这里也对递归进行了优化,相等则不进行递归
            subs2_1 = s2.substr(len2-i, i);
            subs2_2 = s2.substr(0,len2-i);
            bool is2 = (subs1_1==subs2_1?true:isScramble(subs1_1, subs2_1)) && (subs1_2==subs2_2?true:isScramble(subs1_2, subs2_2));
            if (is1 || is2) return true;//两部分任一部分为Scramble String则s1和s2就为Scramble String
        }
        return false;
    }
};

推荐文章

云计算之分布式计算系统

云计算之分布式计算系统

推荐文章

盲目的”云”

盲目的”云”

推荐文章

荷兰网站遭漏洞攻击,专挑午餐时间启动病毒

荷兰网站遭漏洞攻击,专挑午餐时间启动病毒

推荐文章

Esri中国首席技术官王昊谈 移动GIS 与 云GIS

Esri中国首席技术官王昊谈 移动GIS 与 云GIS

推荐文章

VMware vSphere 5.0中文资料!

VMware vSphere 5.0中文资料!

推荐文章

云主机初体验(盛大云和阿里云)

云主机初体验(盛大云和阿里云)

推荐文章

深度剖析云计算背后采用的技术

深度剖析云计算背后采用的技术

推荐文章

云啊云,云啊云

云啊云,云啊云

推荐文章

论文阅读——Chord原理

论文阅读——Chord原理

推荐文章

膝关节韧带重建手术日记

膝关节韧带重建手术日记

推荐文章

云计算加密

云计算加密

推荐文章

云终端操作系统

云终端操作系统

推荐文章

云计算投资被指变相占土地 需去伪存真

云计算投资被指变相占土地 需去伪存真

推荐文章

夜读2013年度国家信息技术研发选题申报有感

夜读2013年度国家信息技术研发选题申报有感

推荐文章

java在云上的应用

java在云上的应用

推荐文章

RSA2012系列(5):虚拟化安全总揽

RSA2012系列(5):虚拟化安全总揽