C#. Simple approach. (Can someone help me derive the time complexity?)


  • 0
    S
    public class Solution {
        public bool IsScramble(string s1, string s2) {
            int N = s1.Length;
                
                if (N == 1) return s1 == s2;
    
                if (s1 == s2) return true;
    
                for (int i = 0; i < N-1; i++)
                {
                    string s1l = s1.Substring(0, i + 1), s1r = s1.Substring(i + 1);
                    string s2l = s2.Substring(0, i + 1), s2r = s2.Substring(i + 1);
    
                    if (cmp(s1l, s2l) && cmp(s1r, s2r))
                    {
                        if (IsScramble(s1l, s2l) && IsScramble(s1r, s2r))
                            return true;
                    }
    
                    s2r = s2.Substring(N - i - 1); s2l = s2.Substring(0, N - i-1);
    
                    if (cmp(s1l, s2r) && cmp(s1r, s2l))
                    {
                        if (IsScramble(s1l, s2r) && IsScramble(s1r, s2l))
                            return true;
                    }
                }
                return false;
        }
        
        public bool cmp(string s1, string s2)
        {
            char[] a = s1.ToCharArray(), b = s2.ToCharArray();
            Array.Sort(a); Array.Sort(b);
            s1 = new String(a); s2 = new String(b);
            return s1 == s2;
        }
    }

Log in to reply
 

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