8ms C++ solution using BFS, with explanation


  • 120
    G

    If we expand the two strings s1 and s2 into a chessboard, then this problem can be transferred into a path seeking problem from the top-left corner to the bottom-right corner. The key is, each cell (y, x) in the board corresponds to an interval between y-th character in s1 and x-th character in s2. And adjacent cells are connected with like a grid. A BFS can then be efficiently performed to find the path.

    Better to illustrate with an example here:

    Say s1 = "aab" and s2 = "abc". s3 = "aaabcb". Then the board looks like

    o--a--o--b--o--c--o
    |     |     |     |
    a     a     a     a
    |     |     |     |
    o--a--o--b--o--c--o
    |     |     |     |
    a     a     a     a
    |     |     |     |
    o--a--o--b--o--c--o
    |     |     |     |
    b     b     b     b
    |     |     |     |
    o--a--o--b--o--c--o
    

    Each "o" is a cell in the board. We start from the top-left corner, and try to move right or down. If the next char in s3 matches the edge connecting the next cell, then we're able to move. When we hit the bottom-right corner, this means s3 can be represented by interleaving s1 and s2. One possible path for this example is indicated with "x"es below:

    x--a--x--b--o--c--o
    |     |     |     |
    a     a     a     a
    |     |     |     |
    o--a--x--b--o--c--o
    |     |     |     |
    a     a     a     a
    |     |     |     |
    o--a--x--b--x--c--x
    |     |     |     |
    b     b     b     b
    |     |     |     |
    o--a--o--b--o--c--x
    

    Note if we concatenate the chars on the edges we went along, it's exactly s3. And we went through all the chars in s1 and s2, in order, exactly once.

    Therefore if we view this board as a graph, such path finding problem is trivial with BFS. I use an unordered_map to store the visited nodes, which makes the code look a bit complicated. But a vector should be enough to do the job.

    Although the worse case timeis also O(mn), typically it doesn't require us to go through every node to find a path. Therefore it's faster than regular DP than average.

    struct MyPoint {
        int y, x; 
        bool operator==(const MyPoint &p) const {
            return p.y == y && p.x == x;
        }
    };
    namespace std {
        template <>
        struct hash<MyPoint> {
            size_t operator () (const MyPoint &f) const {
                return (std::hash<int>()(f.x) << 1) ^ std::hash<int>()(f.y);
            }
        };
    }
    
    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            if (s1.size() + s2.size() != s3.size()) return false;
    
            queue<MyPoint> q;
            unordered_set<MyPoint> visited;
            bool isSuccessful = false;
            int i = 0;
    
            q.push(MyPoint { 0, 0 });
            q.push(MyPoint { -1, -1 });
            while (!(1 == q.size() && -1 == q.front().x)) {
                auto p = q.front();
                q.pop();
                if (p.y == s1.size() && p.x == s2.size()) {
                    return true;
                }
                if (-1 == p.y) {
                    q.push(p);
                    i++;
                    continue;
                }
                if (visited.find(p) != visited.end()) { continue; }
                visited.insert(p);
    
                if (p.y < s1.size()) { // down
                    if (s1[p.y] == s3[i]) { q.push(MyPoint { p.y + 1, p.x }); }
                }
                if (p.x < s2.size()) { // right 
                    if (s2[p.x] == s3[i]) { q.push(MyPoint { p.y, p.x + 1 }); }
                }
            }
            return false;
        }
    };

  • 0
    B

    So elegant solution!!


  • 0
    G

    hint: you can vote it up :DDD


  • 7
    C

    I came up with a quite similar solution after my recursive solution exceeded the time limit. The trickiest part was getting the indices right. 5 ms:

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            typedef pair<int, int> index;
            unordered_set<int> visited;
            queue<index> q;
            q.push(index(-1, -1));
            
            int cols = s2.size() + 1;
            while (!q.empty()) {
                index idx = q.front();
                q.pop();
                
                int i = idx.first + 1;
                int j = idx.second + 1;
                
                if (i == s1.size() && j == s2.size()) {
                    return i + j == s3.size();
                }
                
                if (i + j < s3.size()) {
                    char next = s3[i + j];
                    if (i < s1.size() && s1[i] == next) {
                        if (visited.insert((i + 1) * cols + j).second) {
                            q.push(index(i, j - 1));
                        }
                    }
                    if (j < s2.size() && s2[j] == next) {
                        if (visited.insert(i * cols + j + 1).second) {
                            q.push(index(i - 1, j));
                        }
                    }
                }
            }
            
            return false;
        }
    };

  • 1
    L

    the idea is novel enough for a vote. and thanks to the graph, the idea is illustrative and easy to understand


  • 0
    Q
    This post is deleted!

  • 0
    M
    This post is deleted!

  • 0
    K

    nice algorithm. however, its not necessarily faster than DP method since they are both O(nm) in time complexity. Your algorithm may skip some cells but has more operations in each step than DP. that's why we only talk about complexity in big O notations.


  • 0
    K

    You could use std::pair instead of defining own Point class.


  • 0
    P

    I find it more difficult than DP but still worth a read :)


  • 4

    Thanks for your sharing! I rethink BFS by your inspiration. I thought it is usually applicable for Min/Shortest problem. Why it works here? I assume the recursive tree for this problem is very "skinny", since branch appears only when s1[0]=s2[0]=s3[0] and then it only splits out 2 children. Here is my Java BFS solution for anyone's reference. Forgive that Java has no built-in Tuple class making code a little messy...

        public boolean isInterleave(String s1, String s2, String s3) {
            if (s1.length() + s2.length() != s3.length()) return false;
            boolean[][] visited = new boolean[s1.length() + 1][s2.length() + 1];
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{0, 0});
            while (!queue.isEmpty()) {
                int[] p = queue.poll();
                if (visited[p[0]][p[1]]) continue;
                if (p[0] == s1.length() && p[1] == s2.length()) return true;
                
                if (p[0] < s1.length() && s1.charAt(p[0]) == s3.charAt(p[0] + p[1]))
                    queue.offer(new int[]{p[0] + 1, p[1]});
                if (p[1] < s2.length() && s2.charAt(p[1]) == s3.charAt(p[0] + p[1]))
                    queue.offer(new int[]{p[0], p[1] + 1});
                visited[p[0]][p[1]] = true;
            }
            return false;
        }
    

Log in to reply
 

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