LeetCode

maximal-rectangle-in-histogram.md

Error in user YAML: (<unknown>): mapping values are not allowed in this context at line 2 column 6

---
layout:none
title: maximal rectangle in histogram
---

Question: Given n non-negative integers representing the histogram's bar height where the width of each bar is 1,
find the area of largest rectangle in the histogram.

Answer:
First, the brute-force solution is obvious. For each integer, find the most left element and right element
which is not less it, that forms the maximal rectangle containing this integer. Iterating the whole array and we
can find the maximal rectangle. The problem is it's two slow because its complexity is O(n2).

We need to optimize it. Here is a hint, for any rectangle that consist of continuous integers, it starts from a
integer which is bigger than its left number and ends with a integer which is bigger than its right number.
So every time we encounter a new integer, if it's bigger than or equal its left value, we can regard it as a start of new
rectangle and if it is smaller than its left value, it must be end of rectangle. We need to store these nested
rectangles and calculate the area when encountering its ending. A stack will just fit our need. Queue or a simple
array are also OK. Here's the code:

int largestRectangleArea(vector<int> &height) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int maxArea = 0;
    stack<int> s;
    height.push_back(0);
    int i = 0; 
    while (i < height.size()) {
        if (s.empty() || height[s.top()] <= height[i]) {
            s.push(i++);
        } else {
            int t = s.top();
            s.pop();
            maxArea = max(maxArea, height[t] * ((s.empty()) ? i : i - s.top() - 1));
        }
    }
    return maxArea;
}

So, when we push another integer into stack we encounter a new rectangle. And when we pop a integer from stack,
we get start position (the next position of the most left value less than it, i.e. the next value on stack) of
one rectangle and can calculate its area. If the stack is empty, which means current value is least value ever,
which forms a rectangle from the start point of the array to current position.

Path Sum

Problem: Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Difficulty: *

Solution: just recursive the tree and if a node is leaf and its val equal current sum value, return true; or find a non null child node of this node and sub sum with this node's value and call the function again.

scramble-string.md

Problem: Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

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". 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". 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.

Notice: if we can only scramble the string once, the problem will be very easy. But in fact, the string can be scramble any times if possible, that make it much difficult.

How do I solve this:

First, suppose the
s1 = a1a2a3a4a5....an-1an; s2 = b1b2b3b4b5....bn-1bn; Then we can remove all the same characters of s1 and s2 at the strings' head and tail. Thus, if a1a2 === b1b2 and an-1an===bn-1bn, the problem of s1 and s2 is equivlent with s1' and s2'. And:
s1' = a3a4a5....an-2; s2' = b3b4b5....bn-2;

Now we know there must be at least one scramble between s1' and s2'. Suppose the scramble point is at index i of s1', and we use function isScrambled(s1,s2) means s2 is a scrambled string of s1. So isScrambled(s1, s2) = isScramble(s1', s2') = (isScramble(s1'[0,i], s2'[0,i]) && isScramble(s1'[i+1, m], s2'[i+1, m]) || (isScramble(s1'[0,i], s2'[m-i,m]) && isScramble(s1'[i+1,m], s2'[0,m-i-1])))

At this point, I realized the preprocess at the beginning to s1 and s2 are also can be concluded into the above formule, so we can solve this problem based on the above formule. Then, how to code?

First, I think of recursive function like this: isScramble(s1, s2) { int n = s1.length(); if (s2.length() != n) return false; if (n == 1) { if (s1[0] == s2[0]) return true; else return false; } for (int i = 0; i < n; i++) { if (isScramble(s1[0,i], s2[0,i]) && isScramble(s1[i+1,n-1], s2[i+1,n-1]) || isScramble(s1[0,i], s2[n-i-1,n-1]) && isScramble(s1[i+1,n-1], s2[0,i])) return true; } return false; }

But it's slow because it contains lots of redundancy computation. For example isScramble(s1[0,1],s2[0,1]) will be recalculated at isScramble(s1[0,2],s2[0,2]) and isScramble(s1[0,3],s2[0,3])..... It's a typical question and we have a typical solution to optimize it: dynamic programming. We can compute isScramble(s1[0,1],s2[0,1]) first and save it, then every time we need it in another computation we just read it. Trading space for time.

Next, we use a 3-dimentional array f[n][n][n] to store all intermediate data and f[i][j][k] means s2[j,j+k] is a scrambled string of s1[i,i+k]. You can check the complete code on my github {leetcode} repository.

Dynamic programming is a general algorithm to solve those problem that may recompute same sub tasks again and again. But it's also not very efficient for some sepcial cases. For example, if there's only one scrambling we can get the right answer very quickly using a special solution. But dynamic programming still iterates all the loops that may be unneccessary.

So I guess if there's a more efficient algorithm that can solve this problem ?
And this problem also reminds me of some related interesting problems:

• how many legal scrambled strings exists for a string s?
• how can find all of them efficiently?

Anyone who have some thoughts about these can mail me. You can find my mail at my github blog.