Stack

• Longest Absolute File Path
• Valid Parentheses

Longest Absolute File Path

注意点： '\t', '\n' 是一个字符，并不是两个字符。分别代表了ascii里面的 09 ht, 32 sp

问题是：求最长的绝对路径长

解法： 要找到最长的路径，需要遍历所有的情况。 路径的长度是由前面的路径加上当前路径的长度组成。 但是当我们退回到上一层目录的时候，我们需要把前面的路径长减去当前的文件夹长度。

所以我们需要一个用一个栈来记录上一层目录的长度，如果我们退出当前文件夹的时候，我们就要把prefixLen减去当前文件夹的长度。

public int lengthLongestPath(String input) {
    String[] tokens = input.split("\n");
    int max = 0;
    int prefixLen = 0;
    Stack<Integer> stack = new Stack<>();

    for(String s:tokens) {
        // count current level
        int level = s.length() - s.replace("\t", "").length();

        // when we are not into deeper level
        // error-prone, pop all upper level 
        while (stack.size() > level) {
            prefixLen -= stack.pop();
        }

        int len = s.replace("\t", "").length() + 1; // add a slash
        prefixLen += len;
        if(s.contains(".")) {
            // - 1 means remove first slash
            if(prefixLen - 1 > max) {
                max = prefixLen - 1;
            }
        }
        stack.push(len);
    }
    return max;
}

Valid Parentheses

Write an algorithm to determine if all of the delimiters in an expression are matched and closed.

Example:

“{ac[bb]}”, “[dklf(df(kl))d]{}” and “{[[]]]}” are matched. But “{3234[fd” and {df][d} are not.

Analyze

Ask interviewer what are all delimiters in this question.

Let’s consider the simplest case. If there’s only one type of delimiter “()”.

Basically, we keep a counter whose initial value is 0. Go over the string, if we get a left parenthesis “(“, increase the counter by 1 and if it’s a right parenthesis “)”, decrease the counter by 1. Finally, if the counter is 0, it means the all the parentheses are balanced.

Let’s generalize the solution for all delimiters.

When I was working on this problem for the first time, what I thought first is to keep separate counters for each delimiter and if all of them are 0 after processing the string, all of the delimiters are balanced. However, this doesn’t work. Consider the case “([)]”, we have an equal number of left and right delimiters but they are incorrectly matched.

Therefore, only keeping the number of unmatched delimiters is not enough, we also need to keep track of all the previous delimiters. Since each time when we see a new delimiter, we need to compare this one with the last unmatched delimiter, stack is the data structure we should consider.

So the solution is:

• Start with an empty stack to store any delimiter we are processing
• Go over the string, for each delimiter we find:
  • If it’s a left parenthesis, push it to the stack
  • If it’s a right parenthesis, pop the top element of the stack and compare with the right parenthesis. If they are matched, keep processing the string. Otherwise, delimiters are not balanced.

Code

public class Solution {
    public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<>();
        Stack<Character> stack = new Stack<>();

        map.put('(',')');
        map.put('[',']');
        map.put('{','}');

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(map.containsKey(c)) {
                stack.push(c);
            } else {
                // Don’t forget to check boundaries. In the coding solution, it’s important to check if the stack is empty.
                if(stack.isEmpty()) {
                    return false;
                } else if(map.get(stack.peek()) == c) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();       
    }
}