LeetCode 87 Scramble String (C++, Python)

-
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.
Solutoin C++


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
private:
    bool intIsScramble(string& s1, string& s2, int i, int j, int l, vector<vector<vector<char>>>& cache) {
        if (cache[i][j][l] != 'U') {
            return cache[i][j][l] != 0;
        }
        
        bool equal = true;
        for (int k = 0; k < l; ++k) {
            if (s1[i + k] != s2[j + k]) {
                equal = false;
                break;
            }
        }
        if (equal) {
            cache[i][j][l] = 1;
            return true;
        }

        size_t hash1 = 0;
        size_t hash2 = 0;
        auto charhash = hash<char>();
        for (int k = 0; k < l; ++k) {
            hash1 ^= charhash(s1[i + k]);
            hash2 ^= charhash(s2[j + k]);
        }
        if (hash1 != hash2) {
            cache[i][j][l] = 0;
            return false;
        }

        for (int k = 1; k < l; ++k) {
            if (intIsScramble(s1, s2, i, j, k, cache) && intIsScramble(s1, s2, i + k, j + k, l - k, cache)) {
                cache[i][j][l] = 1;
                return true;
            }
            if (intIsScramble(s1, s2, i + l - k, j, k, cache) && intIsScramble(s1, s2, i, j + k, l - k, cache)) {
                cache[i][j][l] = 1;
                return true;
            }
        }

        cache[i][j][l] = 0;
        return false;
    }

public:
    bool isScramble(string s1, string s2) {
        if (s1.length() != s2.length()) return false;
        vector<vector<vector<char>>> cache(s1.length(), vector<vector<char>>(s1.length(), vector<char>((s1.length() + 1), 'U')));
        return intIsScramble(s1, s2, 0, 0, s1.length(), cache);
    }
};
Solution Python


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def intIsScramble(self, s1, s2, cache):
        if s1 == s2: return True
        if (s1, s2) in cache:
            return cache[(s1, s2)]
        hash1 = 0
        hash2 = 0
        for i in range(len(s1)):
            hash1 ^= hash(s1[i])
            hash2 ^= hash(s2[i])
        if hash1 != hash2:
            cache[(s1, s2)] = False
            return False
        for i in range(1, len(s1)):
            s11 = s1[0:i]
            s12 = s1[i:]
            s21 = s2[0:i]
            s22 = s2[i:]
            if self.intIsScramble(s11, s21, cache) and self.intIsScramble(s12, s22, cache):
                cache[(s1, s2)] = True
                return True
            s11 = s1[len(s1) - i:]
            s12 = s1[0:len(s1) - i]
            if self.intIsScramble(s11, s21, cache) and self.intIsScramble(s12, s22, cache):
                cache[(s1, s2)] = True
                return True
        cache[(s1, s2)] = False
        return False    
    # @param {string} s1
    # @param {string} s2
    # @return {boolean}
    def isScramble(self, s1, s2):
        if len(s1) != len(s2): return False
        cache = {}
        return self.intIsScramble(s1, s2, cache)

Popular posts from this blog

How Django Works (4) URL Resolution

-
Image
Why We Need URL Resolution Theoretically, we could write a single function to process all incoming HTTP requests. It would work well for very simple websites. For any real websites, it would be much more appropriate to categorize HTTP requests based on their URLs and process them separately in different handlers. For example, BASEURL/polls/ would be an application for polls whereas BASEURL/blogs/ would be an application for blogs. This way, different URLs can be considered different logic applications, so we can think of websites in terms of logic applications – a higher level of abstraction that HTTP request/response pairs. Fortunately, many modern web frameworks come default with mechanisms that do the categorization of HTTP requests based on URIs, which spares us the effort of having to reinvent the wheel.   Django's URL Resolution The official Django document has following description about how Django processes a request. https://docs.djangoproject.com/en/1.8/topic...
Read more

Python Class Method and Class Only Method

-
In this post, I will be discussing Python method especially class method. Example class Foo : def bar_inst ( self ): print ( self , "This is bar_inst" ) @staticmethod def bar_static (): print ( "This is bar_static" ) @classmethod def bar_class (cls): print (cls, "This is bar_class" ) >>> foo = Foo() >>> foo.bar_inst <bound method Foo.bar_inst of <test.Foo object at 0x025A0EB0>> >>> foo.bar_static <function Foo.bar_static at 0x025A34F8> >>> foo.bar_class <bound method type.bar_class of <class 'test.Foo'>> foo.bar_static just returns a function object as if bar_static were defined outside of class. (In Python 2, it would return an unbound method; Python 3 has removed the concept of unbound methods. So a function is either a bound method or a regular function object) How It Works -- Descriptor  Every ...
Read more

How Django works (3): Testing Server and Static Files Serving

-
How Django Handles Static Files By default, Django installs an Application django.contrib.staticfiles, which is responsible for handling requests to files under STATIC_URL.   INSTALLED_APPS = ( 'django.contrib.admin' , 'django.contrib.auth' , 'django.contrib.contenttypes' , 'django.contrib.sessions' , 'django.contrib.messages' , 'django.contrib.staticfiles' , 'polls' , ) STATIC_URL = '/static/' This method is grossly inefficient and probably insecure, so it is unsuitable for production. https://docs.djangoproject.com/en/1.8/howto/static-files/deployment/ How staticfiles App Works Based on the first blog of Django series, Django interacts with web servers by providing a callable application that conforms to WSGI specification. 1 2 3 4 5 class WSGIHandler (base . BaseHandler): initLock = Lock() request_class = WSGIRequest def __call__ ( self , environ, start_...
Read more