Question

link

    3
   / \
  9  20
    /  \
   15   7

[
  [3],
  [20,9],
  [15,7]
]

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is based on “Binary Tree Level Order Traversal”.

Altough this is difficulty level 4, the real difficult part is solving “Binary Tree Level Order Traversal”. If that question is solved, only slight modification is needed for this question.

Solution

Instead of using queue like in “Binary Tree Level Order Traversal”, this question is solved by using Stack. And it’s not hard to see why. The only additional things to note:

1. There is no ‘single stack solution’, we must use 2 stacks. (because when push, it’s pushed to top).

2. Keep a boolean variable to remember rightToLeft or leftToRight.

Code

First, standard BFS solution using 2 stacks.

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    if (root == null) return ans;
    Stack<TreeNode> q = new Stack<TreeNode>();
    q.push(root);
    boolean reverse = true;
    while (! q.isEmpty()) {
        ans.add(new ArrayList<Integer>());
        Stack<TreeNode> qq = new Stack<TreeNode>();
        int curSize = q.size();
        for (int i = 0; i < curSize; i ++) {
            TreeNode node = q.pop();
            ans.get(ans.size() - 1).add(node.val);
            if (reverse) {
                if (node.left != null) qq.push(node.left);
                if (node.right != null) qq.push(node.right);
            }
            else {
                if (node.right != null) qq.push(node.right);
                if (node.left != null) qq.push(node.left);
            }
        }
        q = qq;
        reverse = ! reverse;
    }
    return ans;
}

Second, DFS solution written by me, and yes, I love DFS more.

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    helper(ans, root, 1);
    return ans;
}

private void helper(ArrayList<ArrayList<Integer>> ans, TreeNode node, int level) {
    if (node == null) return;
    if (ans.size() < level) {
        ArrayList<Integer> lv = new ArrayList<Integer>();
        lv.add(node.val);
        ans.add(lv);
    }
    else {
        if (level % 2 == 0) 
            ans.get(level - 1).add(0, node.val);
        else
            ans.get(level - 1).add(node.val);
    }
    helper(ans, node.left, level + 1);
    helper(ans, node.right, level + 1);
}

Question

link

    3
   / \
  9  20
    /  \
   15   7

[
  [15,7]
  [9,20],
  [3],
]

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is the same question as previous one.

Solution

There are also 2 solution: BFS and DFS.

I post BFS code below. Only 2 lines are different: ans.get() and ans.add().

Code

public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    if (root == null) return ans;
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.add(root);
    while (! q.isEmpty()) {
        ans.add(0, new ArrayList<Integer>());
        int curSize = q.size();
        for (int i = 0; i < curSize; i ++) {
            TreeNode node = q.remove();
            ans.get(0).add(node.val);
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
    }
    return ans;
}

Question

link

    3
   / \
  9  20
    /  \
   15   7

[
  [3],
  [9,20],
  [15,7]
]

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a really classic question.

It is not difficult, however, it’s important to understand 2 different ways to solve this problem: DFS and BFS.

The different between Inorder, preorder, postorder and Level-order is explained very well in this post.

pre-order, in-order, and post-order tree traversal are called Depth First Search (DFS), since they visit the tree by proceeding deeper and deeper until it reaches the leaf nodes.

DFS uses a data structure called Stack and is commonly implemented using recursion. If recursion is not allowed, we can simulate the recursion by using iterative method with the help of stack. For example in the question “Binary Search Tree In-Order Traversal”, we have a iterative DFS solution using a stack.

The most natural solution for level-order traversal is Breadth First Search (BFS), since it visits the nodes level by level. BFS requires the use of a data structure called Queue.

To summarize, Inorder, preorder and postorder is DFS implemented by Stack. Level-order is BFS implemented by Queue. It is very important to forever make it clear and take it into your grave 60 years later (maybe more, if not less).

One mor thing, Stack is a Java class that inherit from Vector.

The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.

ArrayList is roughly equivalent to Vector, except that it is unsynchronized.

However, Queue is an interface, not a class. What is the most popular Queue implementation in Java? It is not PriorityQueue, it’s LinkedList!

Solution

As said, level-order is BFS. The first code posted below is implemented with a queue. A lot of people used 2 queues, which I don’t like.

Second code is DFS. This is my initial solution, maybe because I’m more familiar with DFS.

Code

First, BFS code using 1 queue

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    if (root == null) return ans;
    int level = 0;
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.add(root);
    while (! q.isEmpty()) {
        ans.add(new ArrayList<Integer>());
        int curSize = q.size();
        for (int i = 0; i < curSize; i ++) {
            TreeNode node = q.remove();
            ans.get(level).add(node.val);
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        level ++;
    }
    return ans;
}

First code revised: I do not really need the variable ‘level’.

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    if (root == null) return ans;
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.add(root);
    while (! q.isEmpty()) {
        ans.add(new ArrayList<Integer>());
        int curSize = q.size();
        for (int i = 0; i < curSize; i ++) {
            TreeNode node = q.remove();
            ans.get(ans.size() - 1).add(node.val);
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
    }
    return ans;
}

Second, DFS code

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    if (root == null) return ans;
    traverse(ans, root, 0);
    return ans;
}

private void traverse (ArrayList<ArrayList<Integer>> ans, TreeNode node, int level) {
    if (node == null) return;
    if (ans.size() >= level + 1) 
        ans.get(level).add(node.val);
    else {
        ArrayList<Integer> temp = new ArrayList<Integer>();
        temp.add(node.val);
        ans.add(temp);
    }
    traverse(ans, node.left, level + 1);
    traverse(ans, node.right, level + 1);
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is question can be solved by either DFS or Brute Force, both are fine.

Solution

The DFS solution is obvious, I have the code for it.

However, there’s another person who wrote much less code while implementing the same solution as mine. I will post his code as a good example to learn.

The brute force solution in this case does not sound like a bad idea. This is the most top-rated idea on official forum as well.

You can get points' positions by i, j, k. Using these positions, you can divide s into candidate ip-form. Then, you can judge whether the candidate fits ip. To improve the efficiency, you can narrow the scope of i, j, k.

So, this BF code is also posted below.

Just one more thing. I tested the exact same BF code written in C++. Compared to the 420ms it took Java to pass OJ test, C++ takes 8ms only! I was a bit shocked.

Code

First, DFS, my code

Note: I could have just insert as string, so that convert() method would not be needed.

public ArrayList<String> restoreIpAddresses(String s) {
    ArrayList<String> ans = new ArrayList<String>();
    helper(ans, new ArrayList<String>(), s, 0);
    return ans;
}

private void helper(ArrayList<String> ans, ArrayList<String> cur, String s, int from) {
    int len = s.length();
    if (from >= len) return;
    if (cur.size() == 3) {
        String lastStr = s.substring(from);
        if (isValidIpNumber(lastStr)) {
            ArrayList<String> oneAns = new ArrayList<String>(cur);
            oneAns.add(lastStr);
            ans.add(convert(oneAns));
        }
    }
    else {
        // cur.size less than 3, so get next num (length = 1, 2 or 3)
        for (int i = 1; i <= 3 && from + i <= len; i ++) {
            String nextStr = s.substring(from, from + i);
            if (isValidIpNumber(nextStr)) {
                cur.add(nextStr);
                helper(ans, cur, s, from + i);
                cur.remove(cur.size() - 1);
            }
        }
    }
}

private boolean isValidIpNumber(String str) {
    if (str.length() == 0 || str.length() > 3) return false;
    if (str.charAt(0) == '0' && str.length() != 1) return false;
    int num = Integer.parseInt(str);
    return (0 <= num && num <= 255);
}

private String convert(ArrayList<String> l) {
    String ans = "";
    for (String a: l)
        ans += "." + a;
    return ans.substring(1);
}

Second, DFS, shorter version code

public ArrayList<String> restoreIpAddresses(String s) {
    ArrayList<String> res = new ArrayList<String>();  
    if (s.length()<4||s.length()>12) return res;  
    dfs(s,"",res,0);  
    return res;  
}  

public void dfs(String s, String tmp, ArrayList<String> res, int count){  
    if (count == 3 && isValid(s)) {  
        res.add(tmp + s);  
        return;  
    }  
    for(int i=1; i<4 && i<s.length(); i++){  
        String substr = s.substring(0,i);  
        if (isValid(substr)){  
            dfs(s.substring(i), tmp + substr + '.', res, count+1);  
        }  
    }  
}  

public boolean isValid(String s){  
    if (s.charAt(0)=='0') return s.equals("0");  
    int num = Integer.parseInt(s);  
    return num<=255 && num>0;  
}  

Third, BF code using triple nested loop (Java)

public ArrayList<String> restoreIpAddresses(String s) {
    ArrayList<String> res = new ArrayList<String>();  
    if (s.length() > 12 || s.length() < 4) return res;
    for (int i = 1; i < 4; i ++) {
        String first = s.substring(0, i);
        if (! isValid(first)) continue;
        for (int j = 1; i + j < s.length() && j < 4; j ++) {
            String second = s.substring(i, i + j);
            if (! isValid(second)) continue;
            for (int k = 1; i + j + k < s.length() && k < 4; k ++) {
                String third = s.substring(i + j, i + j + k);
                String fourth = s.substring(i + j + k);
                if (isValid(third) && isValid(fourth)) 
                    res.add(first + "." + second + "." + third + "." + fourth);
            }
        }
    }
    return res;
}  

public boolean isValid(String s) {
    if (s.length() > 1 && s.charAt(0) == '0') return false;
    return 0 <= Integer.parseInt(s) && Integer.parseInt(s) <= 255;  
}

Fourth, same BF code (C++)

vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    if (s.size() > 12 || s.size() < 4) return res;
    for (int i=1; i<4; i++) {
        string first = s.substr(0, i);
        if (!isValid(first)) continue;
        for (int j=1; i+j < s.size() && j<4; j++) {
            string second = s.substr(i, j);
            if (!isValid(second)) continue;
            for (int k=1; i+j+k < s.size() && k<4; k++) {
                string third = s.substr(i+j, k);
                string fourth = s.substr(i+j+k);
                if (isValid(third) && isValid(fourth)) {
                    string temp = first+"."+second+"."+third+"."+fourth;
                    res.push_back(temp);
                }
            }
        }
    }
    return res;
}

bool isValid(string s) {
    if (s.size() > 1 && s[0] == '0') return false;
    if (stoi(s) <= 255 && stoi(s) >= 0) return true;
    else return false;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very difficult question. It is similar and also related to “Largest Rectangle in Histogram”.

Two solutions are available for this question.

First solution is O(n²). This makes use of solution of “Largest Rectangle in Histogram”, which is to say, we are finding the max rectangle for each row (as base) in the matrix.

This solution is very easy to write once you realize this connection - I guess not many people would. That’s why I have the next solution.

Second solution is a clever Brute Force, time complexity is O(n³). The fundamental idea is to make a 2-D array storing the number of ‘1’s occured before current node (inclusive). After this is done, there’re 2 different ways to implement. Read code 2 and code 3.

Solution

FIrst code is easy.

Second code is the idea from this blog. For every node in the 2-D array, checks all possible rectangles ending at this node (which mean check all the way up/left).

Third code from this blog. It is similar to second, but it’s checking all rectangles that shared same width as current line. So it’s checking up then down, both direction. Read the code and it’s easy to understand.

Code

First, solution making use of “Largest rectangle”

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0 || matrix[0].length == 0) return 0;
    int[][] m = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i ++) {
        for (int j = 0; j < matrix[i].length; j ++) {
            if (i == 0 || matrix[i][j] == '0') 
                m[i][j] = matrix[i][j] - '0';
            else 
                m[i][j] = m[i-1][j] + 1;
        }
    }
    int max = 0;
    for (int i = 0; i < m.length; i ++) {
        max = Math.max(max, largestRectangleArea(m[i]));
    }
    return max;
}

// the following code is the solution for "Largest Rectangle in Histogram"
public int largestRectangleArea(int[] height) {
    int len = height.length;
    if (len == 0) return 0;
    int max = Integer.MIN_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < len; i ++) {
        if (stack.isEmpty() || height[stack.peek()] <= height[i]) stack.push(i);
        else {
            int temp = stack.pop();
            // here I must do a check of stack.isEmpty(), 
            // And do nto use (i-height[temp]) instead use (i-stack.peek()-1])
            max = Math.max(max, height[temp] * 
                (stack.isEmpty() ? i : (i - stack.peek() - 1)));
            i --;
        }
    }
    while (! stack.isEmpty()) {
            int temp = stack.pop();
            max = Math.max(max, height[temp] * 
                (stack.isEmpty() ? len : (len - stack.peek() - 1)));
    }
    return max;
}

Second

public int maximalRectangle(char[][] matrix) {
    int rows = matrix.length;  
    if (rows == 0) return 0;  
    int cols = matrix[0].length;  
    int [][] hOnes = new int[rows][cols];
    int max = 0;
    for (int i=0; i<rows; i++)
        for(int j=0; j<cols; j++) 
            if(matrix[i][j] == '1')
                if(j == 0) hOnes[i][j] = 1;
                else hOnes[i][j] = hOnes[i][j-1] + 1;
    for (int i=0; i<rows; i++)
        for (int j=0; j<cols; j++){  
            if (hOnes[i][j] != 0){  
                int minI = i;
                int minRowWidth = hOnes[i][j];
                while (minI >= 0){
                    minRowWidth = Math.min(minRowWidth, hOnes[minI][j]);  
                    int area = minRowWidth * (i-minI+1);  
                    max = Math.max(max, area);  
                    minI--;  
                }
            }
        }
    return max;  
}

Third

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;
    int res = 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] d = new int[m][n];
    for (int i = 0; i < m; i++) {
        d[i][0] = matrix[i][0] - '0';
        for (int j = 1; j < n; j++) 
            d[i][j] = matrix[i][j] == '1' ? d[i][j - 1] + 1 : 0;
    }
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++) 
            res = Math.max(res, expand(d, i, j));
    return res;
}

private int expand(int[][] d, int I, int J) {
    int height = 0, width = d[I][J];
    //go up
    for (int i = I - 1; i >= 0; i--)
        if (d[i][J] >= width) height++;
        else break;
    //go down
    for (int i = I; i < d.length; i++) 
        if (d[i][J] >= width) height++;
        else break;
    return width * height;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a DP question.

At first look it might look like very easily solved by DFS. It it, but TLE exception.

So, I learnt the idea from this blog. It’s easy to realize this is a very standard DP question.

Solution

Declare a 2-D array for DP, and dp(i)(j) denotes whether it’s possible to construct s3 (of length i+j) by using s1 (of length i) and s2 (of length j).

Only thing needs to mention is the size of dp is (m+1)*(n+1), because i = [0, m] and j = [0, n].

Code

DP solution

public boolean isInterleave(String s1, String s2, String s3) {
    int len1 = s1.length();
    int len2 = s2.length();
    int len3 = s3.length();
    if (len1 + len2 != len3) return false;
    boolean[][] dp = new boolean[len1 + 1][len2 + 1];
    dp[0][0] = true;
    for (int i = 1; i <= len2; i ++)
        dp[0][i] = dp[0][i - 1] & s2.charAt(i-1) == s3.charAt(i-1);
    for (int i = 1; i <= len1; i ++)
        dp[i][0] = dp[i-1][0] & s1.charAt(i-1) == s3.charAt(i-1);
    for (int i = 1; i <= len1; i ++) {
        for (int j = 1; j <= len2; j ++) {
            if (s1.charAt(i-1) == s3.charAt(i+j-1) && dp[i-1][j])
                dp[i][j] = true;
            if (s2.charAt(j-1) == s3.charAt(i+j-1) && dp[i][j-1])
                dp[i][j] = true;
        }
    }
    return dp[len1][len2];
}

Question

link

   1
    \
     2
    /
   3

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is a classic AND EXTREMELY IMPORTANT question.

Solution is well explained in this blog:

First, the current pointer is initialized to the root. Keep traversing to its left child while pushing visited nodes onto the stack. When you reach a NULL node (ie, you’ve reached a leaf node), you would pop off an element from the stack and set it to current. Now is the time to print current’s value. Then, current is set to its right child and repeat the process again. When the stack is empty, this means you’re done printing.

Code

concise code, hard to think of

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> ans = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode p = root;
    while (p != null || ! stack.isEmpty()) {
        if (p != null) {
            stack.push(p);
            p = p.left;
        }
        else if (! stack.isEmpty()) {
            TreeNode temp = stack.pop();
            ans.add(temp.val);
            p = temp.right;
        }
    }
    return ans;
}

more intuitive code, written by Oct 8th, 2014

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<Integer>();
    if (root == null) {
        return ans;
    }

    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode p = root;
    while (p != null) {
        stack.push(p);
        p = p.left;
    }
    while (!stack.isEmpty()) {
        p = stack.pop();
        ans.add(p.val);
        p = p.right;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
    }
    return ans;
}

Question

link

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

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

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

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is problem can be solved by either DFS or DP.

This blog have a very good analysis of the DFS approach.

Note that the binary tree can be constructed arbitrarily. So the general idea to tackle this problem is to enumerate every possible binary trees using DFS to see if two strings are scrambled strings. We can accelerate this process by adding a very efficient pruning.
Given two strings, s1, s2. First check if they have same letters and same length, denote as len.
For any l (1 <= l <= len): partition s1 into s11 = s1[0 : l), s12 = s1[l : len). We have two ways to partition s1:

1. s21 = s2[0 : 1), s22 = s2[l : len). In this case, check s11 and s21 have same letters and are scrambled strings. And check s12 and s22 have same letters and are scrambled strings
2. s21 = s2[0 : len – l), s22 = s2[len – l : len). In this case, check s11 and s22 have same letters and are scrambled strings. Then check s12 and s21 have same letters and are scrambled strings

This blog have a very good DP analysis.

dp[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble string。
有三种情况需要考虑：
1. 如果两个substring相等的话，则为true
2. 如果两个substring中间某一个点，左边的substrings为scramble string， 同时右边的substrings也为scramble string，则为true
3. 如果两个substring中间某一个点，s1左边的substring和s2右边的substring为scramble string, 同时s1右边substring和s2左边的substring也为scramble string，则为true

For more explanation, this blog and this blog and this blog have discussed about it.

Code

my code

public boolean isScramble(String s1, String s2) {
    if (! sameLetters(s1, s2)) return false;
    if (s1.equals(s2)) return true;
    for (int i = 1; i < s1.length(); i ++) {
        String left1 = s1.substring(0,  i);
        String right1 = s1.substring(i, s1.length());
        String left2 = s2.substring(0,  i);
        String right2 = s2.substring(i, s2.length());
        if (isScramble(left1, left2) && isScramble(right1, right2))
            return true;
        left2 = s2.substring(0, s2.length() - i);
        right2 = s2.substring(s2.length() - i, s2.length());
        if (isScramble(left1, right2) && isScramble(right1, left2))
            return true;
    }
    return false;
}

private boolean sameLetters(String a, String b) {
    if (a.length() != b.length()) return false;
    int[] count = new int[26];
    for (Character aa: a.toCharArray()) 
        count[aa - 'a'] ++;
    for (Character bb: b.toCharArray()) 
        if (count[bb - 'a'] -- <= 0) 
            return false;
    return true;
}

Updated on July 5th, 2014: written again with less substring operations and more variables inside the method:

public boolean isScramble(String s1, String s2) {
    if (s1 == null || s2 == null || s1.length() != s2.length()) {
        return false;
    }
    int len = s1.length();
    return helper(s1, 0, len - 1, s2, 0, len - 1);
}

private boolean helper(String s1, int a1, int b1, String s2, int a2, int b2) {
    if (a1 - b1 != a2 - b2) 
        return false;
    // check s1[a1, b1] and s2[a2, b2] have same set of letters
    int[] count = new int[26];
    for (int i = a1; i <= b1; i++) 
        count[s1.charAt(i) - 'a'] ++;
    for (int i = a2; i <= b2; i++) 
        if (count[s2.charAt(i) - 'a'] -- <= 0) 
            return false;
    // check s1[a1, b1] and s2[a2, b2] is scramble or not
    if (a1 == b1) {
        return (s1.charAt(a1) == s2.charAt(a2));
    }
    for (int i = 0; i < b1 - a1; i++) {
        boolean check = helper(s1, a1, a1 + i, s2, a2, a2 + i) 
                    && helper(s1, a1 + i + 1, b1, s2, a2 + i + 1, b2);
        if (check) return true;
        check = helper(s1, a1, a1 + i, s2, b2 - i, b2) 
                    && helper(s1, a1 + i + 1, b1, s2, a2, b2 - i - 1);
        if (check) return true;
    }
    return false;
}

DP code, not written by me

public boolean isScramble(String s1, String s2) {
    int n = s1.length();
    boolean[][][] dp = new boolean[n][n][n + 1];
    for (int i = n - 1; i >= 0; i--)
        for (int j = n - 1; j >= 0; j--)
            for (int k = 1; k <= n - Math.max(i, j); k++) {
                if (s1.substring(i, i + k).equals(s2.substring(j, j + k)))
                    dp[i][j][k] = true;
                else {
                    for (int l = 1; l < k; l++) {
                        if (dp[i][j][l] && dp[i + l][j + l][k - l] 
                            || dp[i][j + k - l][l] && dp[i + l][j][k - l]) {
                            dp[i][j][k] = true;
                            break;
                        }
                    }
                }
            }
    return dp[0][0][n];
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very standard interview question of LinkedList.

Solution

Keep 2 pointers, one of which points to preReversePosition, another one points to finalTailOfTheReversedPart. Each time, I will get next element and insert it between the 2 pointers mentioned above. See below image for details:

The coding isn’t easy, there can be a lot of details being omitted. Just think of it in this way: in the above picture, 123 is broken away from 45678. Each time, get next element from 45678, and insert it right after 2. Do this 2 times, so that 4,5 are moved. In the end, make 3 point to 6, and solution done.

Code

First, my code

public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode preHead = new ListNode(0);
    preHead.next = head;
    ListNode before = preHead;
    for (int i = 1; i < m; i ++)
        before = before.next;
    ListNode rTail = before.next;
    ListNode cur = before.next.next;
    for (int i = 0; i < n - m; i ++) {
        ListNode temp = cur.next;
        cur.next = before.next;
        before.next = cur;
        cur = temp;
    }
    rTail.next = cur;
    return preHead.next;
}

Second,

A lot of people have similar solutions, so I won’t post any of their code. Reading it won’t help, write it yourself is actually important.

A lot of people have complained about this problem not easy to write.

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is not very difficult, but can be confusing if the code don’t have good logic.

Solution

There is no fancy algorithm solution. I got it wrong in 10 submissions at first. After a few days, I did this problem again and passed with 1 attempt.

So just keep practicing.

Code

my code

public ListNode partition(ListNode head, int x) {
    if (head == null) return head;
    ListNode PH = new ListNode(1);
    PH.next = head;
    ListNode left = PH, preRight = PH, right = head;
    while (right != null) {
        if (right.val < x) {
            if (preRight != left) {
                preRight.next = right.next;
                right.next = left.next;
                left.next = right;
                left = right;
                right = preRight.next;
            } else {
                left = left.next;
                preRight = left;
                right = right.next;
            }
        } else {
            preRight = right;
            right = preRight.next;
        }
    }
    return PH.next;
}