用bit来做subsets

Subsets

nums = [1, 2, 3]

那subsets是[], [3], [2], [1], [1,2,3], [1,3], [2,3],[1,2]。对于每一位来说，可以取或不取，总共有n位，subsets的个数是2 ^ n。

代码里，外层循环代表了总共有多少组subset，每一个subset新建一个ArrayList；内层循环里，我们看当前的数组的第j位是1还是0，如果是1的话，那我们把nums[j]加到当前的list里去。

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        int length = nums.length;
        for (int i = 0; i < (1 << length); i++) {
            List<Integer> list = new ArrayList<Integer>();
            for (int j = 0; j < nums.length; j++) {
                if ((i >> j & 1) == 1) {
                    list.add(nums[j]);
                }
            }
            result.add(list);
        }
        return result;
    }
}

另一个Subsets的迭代的写法。

对于上一层循环的所有的结果，我们在当前循环里deep copy上一层循环的所有结果，并且在新的list里加入当前遍历到的num。

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        result.add(new ArrayList<Integer>());
        for (int i = 0; i < nums.length; i++) {
            int size = result.size();
            for (int j = 0; j < size; j++) {
                List<Integer> newList = new ArrayList<Integer>(result.get(j));
                newList.add(nums[i]);
                result.add(newList);
            }
        }
        return result;
    }
}

Letter Combinations of a Phone Number

这题的迭代的做法跟上一题的subsets的迭代的做法基本是一样的。

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

        String[] strs = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        result.add("");

        for (int i = 0; i < digits.length(); i++) {
            int num = digits.charAt(i) - '0';
            String str = strs[num];
            List<String> nextLvl = new ArrayList<String>();
            for (String s: result) {
                for (int j = 0; j < str.length(); j++) {
                    nextLvl.add(s + str.charAt(j));
                }
            }
            result = nextLvl;
        }
        return result;
    }
}

Permutations

如果当前有一个list是[1,2]，这个时候我们要插入3的话，可以插在index为0,1,2这个三个位置，得到[3,1,2],[1,3,2],[1,2,3]。

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        List<Integer> l = new ArrayList<Integer>();
        l.add(nums[0]);
        result.add(l);
        for (int i = 1; i < nums.length; i++) {
            List<List<Integer>> nextLvl = new ArrayList<List<Integer>>();
            for (List<Integer> list: result) {
                int size = list.size();
                for (int j = 0; j <= size; j++) {
                    List<Integer> newList = new ArrayList<Integer>(list);
                    newList.add(j, nums[i]);
                    nextLvl.add(newList);
                }
            }
            result = nextLvl;
        }
        return result;
    }
}

Generalized Abbreviation

这一题跟subsets是一样的，对于每一个character来说，有两种情况。要不就是append这个character，要不就是变成一个数字，所以总共的可能性也是2 ^ n。

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<String>();
        if (word == null) {
            return result;
        }
        int length = word.length();

        for (int i = 0; i < (1 << length); i++) {
            StringBuffer sb = new StringBuffer();
            int count = 0;
            for (int j = 0; j < length; j++) {
                if ((i >> j & 1) == 1) {
                    if (count != 0) {
                        sb.append(count);
                        count = 0;
                    }
                    sb.append(word.charAt(j));
                } else {
                    count++;
                }
            }
            if (count != 0) {
                sb.append(count);
            }
            result.add(sb.toString());
        }
        return result;
    }
}

Minimum Unique Word Abbreviation

这个做法超时了，待做。

public class Solution {
    public String minAbbreviation(String target, String[] dictionary) {
        if (target == null || target.length() == 0) {
            return target;
        } else if (dictionary == null || dictionary.length == 0) {
            return "" + target.length();
        }
        Set<String> dict = new HashSet<String>();
        for (String word: dictionary) {
            dict.add(word);
        }
        if (dict.contains(target)) {
            return "";
        }

        TrieTree tree = new TrieTree();
        for (String word: dict) {
            List<String> abbr = getAbbr(word);
            for (String s: abbr) {
                tree.insert(s);
            }
        }

        List<String> list = getAbbr(target);
        Queue<String> queue = new PriorityQueue<String>(new Comparator<String>(){
            public int compare(String a, String b) {
                return getLength(a) - getLength(b);
            }
        });

        for (String s: list) {
            queue.offer(s);
        }

        while (!queue.isEmpty()) {
            String s = queue.poll();
            if (!tree.search(s)) {
                return s;
            }
        }
        return "";
    }

    private List<String> getAbbr(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null) {
            return result;
        }

        int length = s.length();
        for (int i = 0; i < (1 << length); i++) {
            StringBuffer sb = new StringBuffer();
            int count = 0;
            for (int j = 0; j < length; j++) {
                if ((i >> j & 1) == 1) {
                    if (count != 0) {
                        sb.append(count);
                        count = 0;
                    }
                    sb.append(s.charAt(j));
                } else {
                    count++;
                }
            }
            if (count != 0) {
                sb.append(count);
            }
            result.add(sb.toString());
        }
        return result;
    }

    private int getLength(String s) {
        int i = 0, count = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int j = i;
                while (j < s.length() && Character.isDigit(s.charAt(j))) {
                    j++;
                }
                i = j;
            } else {
                i++;
            }
            count++;
        }
        return count;
    }
}

class TrieNode {
    Map<Character, TrieNode> map;
    boolean isEnd;

    public TrieNode() {
        map = new HashMap<Character, TrieNode>();
        isEnd = false;
    }
}

class TrieTree {
    TrieNode root;

    public TrieTree() {
        root = new TrieNode();
    }

    public void insert(String s) {
        TrieNode node = root;
        for (char c: s.toCharArray()) {
            if (!node.map.containsKey(c)) {
                node.map.put(c, new TrieNode());
            }
            node = node.map.get(c);
        }
        node.isEnd = true;
    }

    public boolean search(String s) {
        TrieNode node = root;
        for (char c: s.toCharArray()) {
            if (!node.map.containsKey(c)) {
                return false;
            }
            node = node.map.get(c);
        }
        return node.isEnd;
    }
}