LeetCode Day2

LeetCode 14 Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0){
        return "";
    }
    String element = strs[0];
    int j = element.length();
    for (int i = 0;i < strs.length;i++){
        while (strs[i].indexOf(element.substring(0,j)) != 0){
            j--;
            if(j < 0){
                return "";
            }
        }
    }
    return element.substring(0,j);
}

It means we can compare the first two elements and find the longest prefix, then we use it to compare next.

//concice
public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    String element = strs[0];
    for (int i = 0; i < strs.length; i++) {
        while (strs[i].indexOf(element) != 0) {
            element = element.substring(0, element.length() - 1);
            if (element.isEmpty()) {
                return "";
            }
        }
    }
    return element;
}

LeetCode 20 Valid Parentheses

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

One solution is like this, quite simple and smart

public boolean isValid(String s) {
    while (s.contains("[]") || s.contains("{}") || s.contains("()")){
        s = s.replace("[]","");
        s = s.replace("{}","");
        s = s.replace("()","");
    }
    return s.equals("");
}

Another Solution which use stack may more efficiently

Stack<Character> stack = new Stack<>();
     char[] chars = s.toCharArray();

     Map<Character, Character> map = new HashMap();
     map.put(')', '(');
     map.put('}', '{');
     map.put(']', '[');

     for (int i = 0; i < chars.length; i++) {
         if (map.containsKey(chars[i])) {
             char topElement = stack.isEmpty() ? '#' : stack.pop();
             if (topElement != map.get(chars[i])) {
                 return false;
             }
         } else {
             stack.push(chars[i]);
         }
     }

     return stack.empty();