Leetcode-String

Leetcode 3. Longest Substring Without Repeating Characters. 【Green】【Medium】

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null || s.length()==0) return 0;
        Map<Character,Integer> map = new HashMap<>();
        int pointer = 0, res = 0; 
        for(int i=0; i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                pointer = Math.max(pointer,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            res = Math.max(res,i-pointer+1);
        }
        return res;
    }
}

Leetcode 301
题目简介：删除不合理的括号，返回的是List<String>, 包含所有删除后合理的String。
解答过程：写一个helper函数，注意用一个char[] check = {'(', ')'} ，一个 i 来记录遍历位置，一个 j 来记录 valid 和 非valid的边界，或者说 delete操作需要检查的起点。
Time: 不确定
Space: O(n).

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        char[] check = new char[]{'(', ')'};
        dfs(s, res, check, 0, 0);
        return res;
    }

    public static void dfs(String s, List<String> res, char[] check, int i, int j) {
        int count = 0;
        //int i = last_i;
        while (i < s.length() && count>= 0) {  //count>=0,若一发现count<0立马跳出循环，在下面for循环处理多余的check[1]
            if (s.charAt(i) == check[0]) count ++;
            if (s.charAt(i) == check[1]) count --;
            i ++;
        }
        // if(count==0 && check[0]=='('){
        //     res.add(s);
        // }
        //System.out.println(i+",//"+count+",/// "+s);
        if (count >= 0)  { // >=0的话，就看看是不是已经reversed，若是就add(第二次reversed)，若不是就reversed后再dfs
            // no extra check[1] is detected. We now have to detect extra check[0] by reversing the string.
            String reversed = new StringBuffer(s).reverse().toString();
            if (check[0] == '(') dfs(reversed, res, new char[]{')', '('}, 0, 0);
            else {
                //check[0]==')'说明经历过了上面的if，从而说明了no extra ')'或者说'('数量>=')';
                //而且进入这里需要count>=0条件,即')'数量>='('
                //两者合并就是'('数量等于')'
                res.add(reversed); 
                //System.out.println("加入res，count="+count+","+check[0]+"//"+reversed);
            }
        }
        else {  // extra check[1] is detected and we have to execute delete operation
            i -= 1; // 'i-1' is the index of abnormal ')' which makes count<0
            
            for (int k = j; k<= i; k++) {
                //System.out.println("count<0,j = "+j);
                if (s.charAt(k) == check[1] && (k == j || s.charAt(k-1) != check[1])) {
                    //System.out.println("count<0,j="+j+"  "+s.substring(0, j)+" // "+s.substring(k+1, s.length()));
                    dfs(s.substring(0, k) + s.substring(k+1, s.length()), res, check, i, k); //唯一能进行delete操作的语句           
                }
            }
        }
    }
}