Any better solution?


  • 17

    My AC code is as below. I think it's not very efficient. Is there any better solution?

    class Solution {
    private:
    	bool anagram(string &s1, string &s2){
    		if(s1.size() != s2.size()) return false;
    		unordered_map<char, int> m;
    		int n = s1.size();
    		for(int i = 0; i < n; ++i){
    			if(m.find(s1[i]) != m.end()){
    				++m[s1[i]];
    			}else{
    				m[s1[i]] = 1;
    			}
    		}
    		for(int i = 0; i < n; ++i){
    			if(m.find(s2[i]) != m.end()){
    				--m[s2[i]];
    				if(m[s2[i]] < 0){
    					return false;
    				}
    			}else{
    				return false;
    			}
    		}
    		return true;
    	}
    public:
        bool isScramble(string s1, string s2) {
        	if(s1.size() != s2.size()) return false;
        	if(s1 == s2) return true;
        	int n = s1.size();
        	for(int i = 1; i < n; ++i){
        		string s11 = s1.substr(0, i);
        		string s12 = s1.substr(i, n - i);
        		string s21 = s2.substr(0, i);
        		string s22 = s2.substr(i, n - i);
        		string s23 = s2.substr(n - i, i);
        		string s24 = s2.substr(0, n - i);
        		if(anagram(s11, s21) && anagram(s12, s22) &&
        			isScramble(s11, s21) && isScramble(s12, s22)
        			||
        			anagram(s11, s23) && anagram(s12, s24) &&
        			isScramble(s11, s23) && isScramble(s12, s24)){
        			return true;
        		}
        	}
            return false;
        }
    };
    

    The main idea is:

    1. separate s1 into two parts, namely --s11--, --------s12--------
    2. separate s2 into two parts, namely --s21--, --------s22--------, and test the corresponding part (s11 and s21 && s12 and s22) with isScramble.
    3. separate s2 into two parts, namely --------s23--------, --s24--, and test the corresponding part (s11 and s24 && s12 and s23) with isScramble.
    4. Note that before testing each sub-part with isScramble, anagram is used first to test if the corresponding parts are anagrams. If not, skip directly.

  • 98
    C
    public class Solution {
        public boolean isScramble(String s1, String s2) {
            if(s1==null || s2==null || s1.length()!=s2.length()) return false;
            if(s1.equals(s2)) return true;
            char[] c1 = s1.toCharArray();
            char[] c2 = s2.toCharArray();
            Arrays.sort(c1);
            Arrays.sort(c2);
            if(!Arrays.equals(c1, c2)) return false;
            for(int i=1; i<s1.length(); i++)
            {
                if(isScramble(s1.substring(0,i), s2.substring(0,i)) && isScramble(s1.substring(i), s2.substring(i))) return true;
                if(isScramble(s1.substring(0,i), s2.substring(s2.length()-i)) && isScramble(s1.substring(i), s2.substring(0, s2.length()-i))) return true;
            }
            return false;
        }
    }
    

    This is my code which is more concise, while the idea is same.


  • 1
    F

    The idea is familiar. But my solution is dp algorithm. The time complexity is O(n^4).

    class Solution:
    # @return a boolean
    def isScramble(self, s1, s2):
        if len(s1) != len(s2):
            return False
        elif len(s1) == 0:
            return True
        LEN = len(s1)
        dp = [[[False] * LEN for start2 in xrange(0, LEN)] for start1 in xrange(0, LEN)]
        for width in xrange(0, LEN):
            for start1 in xrange(0, LEN-width):
                for start2 in xrange(0, LEN-width):
                    if width == 0:
                        if s1[start1] == s2[start2]:
                            dp[start1][start2][width]=True
                    else:
                        for sep in xrange(0, width):
                            if dp[start1][start2][sep] and dp[start1+sep+1][start2+sep+1][width-sep-1]:
                                dp[start1][start2][width]=True
                                break
                            if dp[start1][start2+width-sep][sep] and dp[start1+sep+1][start2][width-sep-1]:
                                dp[start1][start2][width]=True
                                break
        return dp[0][0][LEN-1]

  • -5
    S

    My solution is O(n^3)

    It uses a O(n^3) extra space to save the results of every comparison.
    The comparison here means that whether two strings are scramble to each other, if scramble, the comparison return true, vice versa.

    Its time cost is Sum{k=0 ... n-1} (n-k)(n-k)(k+1) = O(n^3)

    class Solution {
    public:
        typedef vector< vector<bool> > matrix;
        vector<matrix> MAP;
        string str1;
        string str2;
        bool isScramble(string s1, string s2) {
            str1 = s1;
            str2 = s2;
            if(s1.size() != s2.size())
                return false;
            int size = s1.size();
            
            matrix m;
            vector<bool> v;
            v.resize(size, false);
            for(int i=0; i<size; i++)
                m.push_back(v);
            
             for(int i=0; i<size; i++)
                MAP.push_back(m);
            
            for(int i=1; i<=size; i++)
            {
                for(int x=0; x<=size-i; x++)
                {
                    for(int y=0; y<=size-i; y++)
                    {
                        MAP[i-1][x][y] = compare(i, x, y);
                    }
                }
            }
            return MAP[size-1][0][0];
            
        }
        
        bool compare(int substrLen, int s1Pos, int s2Pos)
        {
            int length = substrLen;
            if(length == 1)
                return str1[s1Pos] == str2[s2Pos];
            if(length == 2)
            {
               return (str1[s1Pos]==str2[s2Pos]&&str1[s1Pos+1]==str2[s2Pos+1]) || (str1[s1Pos]==str2[s2Pos+1]&&str1[s1Pos+1]==str2[s2Pos]);
            }
            
            for(int i=1; i<length; i++)
            {
                bool test1 = MAP[i-1][s1Pos][s2Pos] && MAP[length-i-1][s1Pos+i][s2Pos+i];
                if(test1)
                    return true;
                    
                bool test2 = MAP[i-1][s1Pos][s2Pos+length-i] && MAP[length-i-1][s1Pos+i][s2Pos];;
                if(test2)
                    return true;
            }
            return false;
        }
        
    };

  • 0
    C

    According to my calculation, Sum{k=0 ... n-1} (n-k)(n-k)(k+1) = O(n^4)
    The coefficient of n^4 is 1/12.


  • 16
    H

    Here is my solution, which has same idea but a little optimization, and takes nearly 20ms to pass all the tests.

    class Solution {
    private:
        bool isDeformation(string &s1, string &s2)
        {
            if(s1.size() != s2.size())return false;
            int albe[26] = {0};
            for(int i = 0; i < s1.size(); i ++)
                albe[s1[i] - 'a'] ++;
            for(int i = 0; i < s2.size(); i ++)
            {
                albe[s2[i] - 'a'] --;
                if(albe[s2[i] - 'a'] < 0)return false;
            }
            return true;
        }
    public:
        bool isScramble(string s1, string s2) {
            if(isDeformation(s1, s2))
            {
                int len = s1.size();
                if(len <= 3) return true;
                for(int i = 1; i < s1.size(); i ++)
                {
                    string s11 = s1.substr(0, i);
                    string s12 = s1.substr(i, len-i);
                    if(isScramble(s11, s2.substr(0,i)) && isScramble(s12, s2.substr(i, len-i)))
                        return true;
                    if(isScramble(s11, s2.substr(len-i,i)) && isScramble(s12, s2.substr(0, len-i)))
                        return true;
                }
            }
            return false;
        }
    };

  • 0
    M

    This is O(n^4)


  • 0
    G

    my solution is almost identical but cache isScramble result in a hash map, which improves performance as well.


  • 0
    J

    Your function isDeformation() is brilliant!!! I just check whether each character in s1 is in s2, if not, return false. Obviously your method could block out more false cases than mine!!
    I copy and paste your method into mine, and I get optimisation from 80ms to 16ms.


  • 0
    N

    nice coding.


  • 1
    T

    C++ solution with bottom-up dynamic programming.

    class Solution
    {
    public:
    
        bool isScramble(string s1, string s2)
        {
            if (s1.length() != s2.length())
            {
                return false;
            }
    
            if (s1.empty())
            {
                return true;
            }
    
            size_t len = s1.length();
            vector<vector<vector<bool>>> dp(len,
                                            vector<vector<bool>>(len,
                                                                 vector<bool>(len + 1,
                                                                              false)));
    
            for (size_t i = 0; i < len; ++i)
            {
                for (size_t j = 0; j < len; ++j)
                {
                    dp[i][j][1] = (s1[i] == s2[j]);
                }
            }
    
            for (size_t subLength = 2; subLength <= len; ++subLength)
            {
                for (size_t i = 0; i <= (len - subLength); ++i)
                {
                    for (size_t j = 0; j <= (len - subLength); ++j)
                    {
                        for (size_t offset = 0;
                             (offset < (subLength - 1)) && !dp[i][j][subLength];
                             ++offset)
                        {
                            size_t len1 = offset + 1;
                            size_t len2 = subLength - len1;
    
                            dp[i][j][subLength] =
                                (dp[i][j][len1] && dp[i + len1][j + len1][len2]) ||
                                (dp[i][j + len2][len1] && dp[i + len1][j][len2]);
                        }
                    }
                }
            }
    
            return dp[0][0][len];
        }
    };
    

  • 0
    D

    @ hongzhi, your code is great, and I got reminded of the second possiblity from your code. thank you.


  • 0
    E

    use two int with some bit manipulation can do the "isDeformation" work while save some memory.


  • 0
    E

    after some testing, bit manipulation takes too much time that it would TLE lol.


  • 1
    S

    Same recursion idea in Python:

    class Solution:
        # @return a boolean
        def isScramble(self, s1, s2):
            if s1 == s2: return True
            if sorted(s1) != sorted(s2): return False
            
            for i in xrange(1, len(s1)):
                ls1, rs1 = s1[:i], s1[i:]
                ls2, rs2 = s2[:i], s2[i:]
                rls2, rrs2 = s2[:-i], s2[-i:]
                
                if (self.isScramble(ls1, ls2) and self.isScramble(rs1, rs2) or
                        self.isScramble(ls1, rrs2) and self.isScramble(rs1, rls2)):
                    return True
            
            return False

  • 0
    S

    As far as I can tell, T(n) = O(nT(n-1)) = O(n!). Is this correct?


  • 0
    M

    Very elegant!!


  • 44
    D

    A more concise C++ DP version.
    dp[i][j][l] means whether s2.substr(j,l) is a scrambled string of s1.substr(i,l) or not.

    class Solution {
    public:
        bool isScramble(string s1, string s2) {
            int len=s1.size();
            bool dp[100][100][100]={false};
            for (int i=len-1;i>=0;i--)
                for (int j=len-1;j>=0;j--) {
                    dp[i][j][1]=(s1[i]==s2[j]);
                    for (int l=2;i+l<=len && j+l<=len;l++) {
                        for (int n=1;n<l;n++) {
                            dp[i][j][l]|=dp[i][j][n]&&dp[i+n][j+n][l-n];
                            dp[i][j][l]|=dp[i][j+l-n][n]&&dp[i+n][j][l-n];
                        }
                    }
                }
            return dp[0][0][len];
        }
    }; 

  • 0
    J

    My java solution is a bit longer. The basic idea is the same. But with some optimization. I used a single CharCountMap to determine if it's anagram instead of creating new map for every sub-string. also determine anagram in an incremental way
    I also avoid creating many sub strings by using indexes.

    public class Solution {
     	static class CharCountMap extends HashMap<Character, int[]> {
    		public void addChars(char c, boolean add) {
    			int[] i = get(c);
    			if(i == null) {
    				i = new int[1];
    				put(c, i);
    			}
    			i[0] += add ? +1 : -1;
    			if(i[0] == 0)
    				remove(c);
    		}
    	}
    	
    	private static CharCountMap charCountMap;
    
    	public static boolean isScramble(String s1, String s2) {
    		charCountMap = new CharCountMap();
    		if(s1.length() != s2.length())
    			return false;
    		
    		for(char c : s1.toCharArray())
    			charCountMap.addChars(c, true);
    		for(char c : s2.toCharArray())
    			charCountMap.addChars(c, false);
    		if(!charCountMap.isEmpty())
    			return false;
    		
    		return isScramble(s1, 0, s2, 0, s2.length());
    	}
    	
    	private static boolean isScramble(String s1, int p1, String s2, int p2, int length) {
    		if(s1.substring(p1, p1 + length).equals(s2.substring(p2, p2 + length)))
    			return true;
    		
    		for(int i=1; i<length; i++){  //Partition
    			charCountMap.addChars(s1.charAt(p1 + i - 1), true);
    			charCountMap.addChars(s2.charAt(p2 + i - 1), false);
    			if(charCountMap.isEmpty())
    				if(isScramble(s1, p1, s2, p2, i) && isScramble(s1, p1 + i, s2, p2 + i, length - i))
    					return true;
    		}
    		charCountMap.clear();
    		for(int i=1; i<length; i++){  //Partition
    			charCountMap.addChars(s1.charAt(p1 + i - 1), true);
    			charCountMap.addChars(s2.charAt(p2 + length - i), false);
    			if(charCountMap.isEmpty())
    				if(isScramble(s1, p1, s2, p2 + length - i, i) && isScramble(s1, p1 + i, s2, p2, length - i))
    					return true;
    		}
    
    		return false;
    	}
    }

  • 0
    A

    Well done sir


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.