Leetcode Note

use ascii table to solve question

If string consis of all lower english letter, we can define an array of [26]int. 'a' is 97

Ascii Table

Leetcode questions

• 2287
• 2423
• Java Python Ruby Go Solution for 2423

integer to binary string

• 2429

XOR

//try to find x
5^x = 2
5^5^x = 2^5
0^x = 2^5
x=2^5

• XOR Properties
• 2429
• 2425

Linked List

• 2

Set (golang does not have set)

• 2367

Regular Expression

• 2496

Sort String and remove duplicated characters

• 2506

Math

Integer boundary

• 334

Design

• 981
• 2424

Recursive Memoization

• 38

Backtracking

Here is a good explanation for Backtracking. What is Backtracking

One general method to solve combination related backtracking is to use breadth first search tree travesal. I found it is very handy, but may not efficient.

• use a linked list to store element of every level
• initiate the first level
• start a while. Based on the question, decide when to exit the loop
• inside the while loop, level by level using size and poll

Solution for Leetcode 17

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.length()==0) return ans;

        HashMap<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        int l = digits.length();

        LinkedList<String> list = new LinkedList<>();

        int h = 0;

        //the first level
        char c = digits.charAt(h);
        String s = map.get(c);
        for (int i=0; i<s.length(); i++) {
            list.add(Character.toString(s.charAt(i)));
        }

        while (h<l-1) {
            h++;
            int size = list.size();
            for (int i=0; i<size; i++) {
                String s1 = list.poll();
                String toAdd = map.get(digits.charAt(h));

                for (int j=0; j<toAdd.length(); j++) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(s1);
                    sb.append(toAdd.charAt(j));
                    list.add(sb.toString());
                }
            }
        }

       
        while (list.size()>0) {
            ans.add(list.poll());
        }

        return ans;
        
    }
}

Check is Parentheses valid

private boolean isValid(String s) {
        int left = 0, right = 0;
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (c=='(') {
                left++;
            } else {
                right++;
            }

            if (right > left) return false;
        }

        return left==right;
    }