Stack

Valid Parentheses

Link: https://leetcode.com/problems/valid-parentheses/

Code:

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        Stack<Character> stack = new Stack<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                char topChar = stack.isEmpty() ? '#' : stack.pop();
                if (topChar != map.get(c)) return false;
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

• Stack is FILO (First In Last Out);

• Stack methods: push(), pop(), isEmpty();

• HashMap methods: containsKey(), get(), put();

• Time complexity: O(n);

Simplify Path

Link: https://leetcode.com/problems/simplify-path/

Code:

class Solution {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        String[] comp = path.split("/");
        String res = "";
        for (String s : comp) {
            if (!s.equals(".") && !s.isEmpty() && !s.equals("..")) {
                stack.push(s);
            } else if (s.equals("..") && !stack.isEmpty()) {
                stack.pop();
            }
        }
        res += "/";
        for (String s : stack) {
            res += s;
            res += "/";
        }
        return res.length() > 2 ? res.substring(0, res.length()-1) : res;
    }
}

• Stack can not pop when it is empty;

• Java stack method push() vs. add(): see stackoverflow;

• split() method for String;

• equals() method for String;