14. Longest Common Prefix

返回最长公共前缀子串。原题

1
2

Input: ["flower","flow","flight"]
Output: "fl"

水平扫描：

horizontal scanning

从头开始遍历整个数组，并且两两比较LCP。如果第i次比较的结果是空，则停止迭代返回空字符串；否则就直到遍历结束:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public String longestCommonPrefix(String[] strs){
  if (str.length == 0) return "";
  String prefix = strs[0];
  for (int i = 1; i < strs.length; i++){
    while (strs[i].indexOf(prefix) != 0){
      prefix = prefix.substring(0, prefix.length() - 1);
      if (prefix.isEmpty()) return "";
    }
  }
  return prefix;
}
  • 时间复杂度：O(S)
  • 空间复杂度：O(1)

2. 垂直扫描：

水平扫描有个缺点，就是如果很短的string处于数组末尾，那么还是会进行S次比较，性能上差一点。垂直扫描能解决这个问题，也就是比较同一列(每个字符串的每个字符为一列)：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public String longestCommonPrefix(String[] strs){
	if (strs == null || strs.length == 0) return "";
  for (int i = 0; i < strs[0].length(); i++){
    char c = strs[0].charAt(i);
    for (int j = 1; j < strs.length; j++){
      if(i == strs[j].length() || strs[j].charAt(j) != c){
        return strs[0].substring(0, i);
      }
    }
  }
  return strs[0];
}
  • 时间复杂度：O(S)
  • 空间复杂度：O(1)

921.Minimum Add to Make Prentheses Valid

给定只包含小括号的字符串，返回需要多少个(或)使其成为完整的括号表达式。原题

1
2
3
4
5
6
7
8

Input: "())"
Output: 1
Input: "()))(("
Output: 4
Input: "()"
Output: 0
Input: "((("
Output: 3

题目很简单，注意)不能被(关闭，所有有两个pointer，这里的right只会增加，值得注意:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

var minAddToMakeValid = function(str) {
    let left = 0;
    let right = 0;
    for (let i = 0, n = str.length; i < n; i++) {
        if (str.charAt(i) === ')') {
            if (left === 0) {
                right++;
            } else {
                left--;
            }
        } else {
            left++;
        }
    }
    return left + right;
};