71. Simplify Path
用双端队列比 stack 省事很多。收尾的时候注意下，如果字符串为空的话，需要留个 "/" 作为默认情况。
06/19更新：这道题和LC224有一个细节是一样的，就是对于空字符串的处理，很显然你要考虑跳过空字符串，不然会出错，但我觉得这个细节很神奇在于这些空字符串是怎么来的呢？
public class Solution {
public String simplifyPath(String path) {
Deque<String> queue = new LinkedList<>();
String[] array = path.split("/");
for (String str : array) {
if (str.equals(".") || str.equals("")) continue;
if (str.equals("..")) queue.pollFirst();
else queue.offerFirst(str);
}
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
sb.append("/");
sb.append(queue.pollLast());
}
return sb.length() == 0 ? "/" : sb.toString();
}
}
14. Longest Common Prefix
没什么值得一提的算法思路，无脑比较就行了。prefix越来越短
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; ++i) {
int j = 0;
while (j < strs[i].length() && j < prefix.length() && strs[i].charAt(j) == prefix.charAt(j)) {
j++;
}
if (j == 0) return "";
prefix = prefix.substring(0, j);
}
return prefix;
}
}
394. Decode String / Expression Expand
步骤上不麻烦，遇到嵌套的括号，就把原始 String 变成更小的子问题，递归处理就好了。于是这题操作上总共就三件事：
一边扫一边记录当前数字，times 初始化 = 0；
找到当前括号的匹配括号；
括号之间就是一个新的子问题，递归处理之后把结果用循环添加就好了。
public class Solution {
public String decodeString(String s) {
if(s == null || s.length() == 0) return "";
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
int times = 0;
while (i < s.length() && s.charAt(i) != '[') {
times = times * 10 + (s.charAt(i) - '0');
i++;
}
// FIND THE INDEX OF PARENTHESE ']' THAT MATCHES CURRENT '['
int matchIndex = findIndex(s, i);
String repeat = decodeString(s.substring(i + 1, matchIndex));
while (times != 0) {
sb.append(repeat);
times--;
}
i = matchIndex;
} else {
sb.append(ch);
}
}
return sb.toString();
}
private int findIndex(String s, int index) {
int count = 0;
for (;index < s.length(); ++index) {
if (s.charAt(index) == '[') count++;
if (s.charAt(index) == ']') count--;
if (count == 0) break;
}
return index;
}
}
161. One Edit Distance
挺有意思，这个解法应该叫捏软柿子法。
public class Solution {
public boolean isOneEditDistance(String s, String t) {
if (s.length() > t.length()) {
String tmp = s;
s = t;
t = tmp;
}
int diff = t.length() - s.length();
if (diff > 1) return false;
if (diff == 0) {
int count = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) != t.charAt(i)) count++;
}
return count == 1;
}
if (diff == 1) {
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) != t.charAt(i)) {
return s.substring(i).equals(t.substring(i + 1));
}
}
}
return true;
}
}
核心思想是，既然有且只有 1 个位置 mismatch，我们可以直接在找到 mismatch 位置上判断：
让 n, m 为两个 String 的长度
如果 m == n ，mismatch 之后的子字符串一定完全相等；
否则长的那段在 i 之后的 substring 一定与短的以 i 开始的 substring 全等；
如果在循环末尾还没有发现 mismatch，两个字符串末尾必然会有 1 的长度差，否则 S == T.
在字符串 DP 中，原始字符串上的 substring，等价于原始区间内的 subproblem。
public class Solution {
public boolean isOneEditDistance(String s, String t) {
int n = s.length();
int m = t.length();
if(Math.abs(n - m) > 1) return false;
for(int i = 0; i < Math.min(m,n); i++){
if(s.charAt(i) != t.charAt(i)){
if(n == m) return s.substring(i + 1).equals(t.substring(i + 1));
if(n > m) return s.substring(i + 1).equals(t.substring(i));
if(n < m) return s.substring(i).equals(t.substring(i + 1));
}
}
return Math.abs(n - m) == 1;
}
}
402. Remove K Digits
除去k个数，结果要尽量保持小。
思路是，遍历string里的每个数，将结果存进result，如果当前数比result里的数要小，就替换，保留这个较小的数。用k来计数，每次除掉一个k就减1，直到k等于0。
public class Solution {
public String removeKdigits(String num, int k) {
int digits = num.length() - k;
char[] result = new char[num.length()];
int top = 0;
for (int i = 0; i < num.length(); ++i) {
char c = num.charAt(i);
while (top > 0 && result[top-1] > c && k > 0) {
top -= 1;
k -= 1;
}
result[top++] = c;
}
// find the index of first non-zero digit
int idx = 0;
while (idx < digits && result[idx] == '0') idx++;
return idx == digits? "0": new String(result, idx, digits - idx);
}
}
well，这题的corner case真是多到自杀。总觉得在哪看过类似的题，就是想不起来，这道题应该到DP或者数组的时候，还有股票问题，那个时候会有很多类似的题，目前就先用stack做这个string题，随便做一下就算了，以后再研究。
06/16更新：if (num.length() == k) return "0"; corner case很多，第一句话处理corner case这个很重要。
public class Solution {
public String removeKdigits(String num, int k) {
if (num == null || num.length() == 0) return "";
if (num.length() == k) return "0";
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < num.length(); ++i) {
int curt = num.charAt(i) - '0';
while (!stack.isEmpty() && k > 0 && curt < stack.peek()) {
stack.pop();
k--;
}
stack.push(curt);
}
while (k > 0) {
stack.pop();
k--;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
sb.reverse();
while (sb.length() > 1 && sb.charAt(0) == '0') sb.deleteCharAt(0);
return sb.toString();
}
}
6. ZigZag Conversion
public class Solution {
public String convert(String s, int numRows) {
char[] c = s.toCharArray();
StringBuffer[] sb = new StringBuffer[numRows];
for (int i = 0; i < numRows; ++i) {
sb[i] = new StringBuffer();
}
int index = 0;
while (index < s.length()) {
for (int i = 0; i < numRows && index < s.length(); ++i) {
sb[i].append(c[index++]);
}
for (int i = numRows - 2; i >= 1 && index < s.length(); --i) {
sb[i].append(c[index++]);
}
}
for (int i = 1; i < numRows; ++i) {
sb[0].append(sb[i]);
}
return sb[0].toString();
}
}
38. Count and Say
public class Solution {
public String countAndSay(int n) {
if (n == 0) return "";
if (n == 1) return "1";
String s = "1";
while (--n > 0) {
char[] c = s.toCharArray();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < c.length; ++i) {
int count = 1;
while (i + 1 < c.length && c[i] == c[i + 1]) {
count++;
i++;
}
sb.append(String.valueOf(count));
sb.append(String.valueOf(c[i]));
}
s = sb.toString();
}
return s;
}
}