Brooke: Backtracking

1.Word Search II

Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently?

public class Solution {
    public TrieNode buildTrie(String[] words){
        TrieNode root = new TrieNode();
        for(int i = 0; i<words.length; i++){
          TrieNode cur = root;
          String word = words[i];
            for(int j = 0; j<word.length(); j++){
                int idx = word.charAt(j) - 'a';
                if(cur.children[idx]==null){
                    cur.children[idx] = new TrieNode();
                }
                cur = cur.children[idx];
            }
            cur.isEnd = true;
        }
        return root;
    }
    public List<String> findWords(char[][] board, String[] words) {
        int m = board.length;
        List<String> ans = new ArrayList<>();
        if(m==0||words.length == 0) 
           return ans;
        int n = board[0].length;
        //build trie
        TrieNode root = buildTrie(words);
        //dfs
        for(int i = 0; i<m; i++){
            for(int j = 0; j < n ; j++){
                dfs(board, new StringBuilder(),root, i, j, ans);
            }
        }
       return ans;
    }
    public void dfs(char[][]board,StringBuilder sb, TrieNode cur, int i, int j,List<String> ans){
        if(i<0||j<0||i>=board.length||j>=board[0].length) return;
        char c = board[i][j];
        if(c!='.'&&cur.children[c-'a']!=null){
            sb.append(board[i][j]);
            board[i][j] ='.';//用于visited 防止重复访问造成cycle
            TrieNode next = cur.children[c-'a'];
            if(next.isEnd && !ans.contains(sb.toString())) ans.add(sb.toString());
            dfs(board,sb,next,i-1,j,ans);
            dfs(board,sb,next,i+1,j,ans);
            dfs(board,sb,next,i,j-1,ans);
            dfs(board,sb,next,i,j+1,ans);
            board[i][j] = c;
            sb.deleteCharAt(sb.length()-1);
        }
    }
    class TrieNode{
        TrieNode[] children;
        public boolean isEnd = false;
        public TrieNode(){
            children = new TrieNode[26];
        }
    }
}

2.Word Squares

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

b a l l
a r e a
l e a d
l a d y

Input:
["area","lead","wall","lady","ball"]

Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "area",
    "lead",
    "lady"
  ]
]

构造word squares，第一行随便选
第二行的第一个字符是第二列的那个字符
第三行的前两个字符是第三列的那列字符
第四行的prefix 是第四列的prefix

public class Solution {
    List<List<String>> ans = new ArrayList<>();
    TrieNode root = null;
    public List<List<String>> wordSquares(String[] words) {
        //give every word a chance to be on top
        root = buildTrie(words);
        List<String> list = new ArrayList<>();
        for(String w: words){
            list.add(w);
            dfs(list,1,words[0].length());
            list.remove(list.size()-1);
        }
        return ans;
    }
    public void dfs(List<String> list, int idx,int n){
        if(idx == n){
            ans.add(new ArrayList<>(list));
            return;
        }
        //construct the prefix need to find
        //use trie to find words that start with those constaints,and dfs for each one of them
        String prefix = "";
        for(String s: list){
            prefix+=s.charAt(idx);
        }
        
        List<String> words = root.findWords(prefix);
        for(String word: words){
            list.add(word);
            dfs(list,idx+1,n);
            list.remove(list.size()-1);
        }

    }

     public TrieNode buildTrie(String[] words){
        TrieNode root = new TrieNode();
        for(int i = 0 ; i < words.length; i++){
            String w = words[i];
            TrieNode cur = root;
            for(int j = 0; j < w.length(); j++){
                int idx = w.charAt(j) - 'a';
                if(cur.children[idx] == null){
                   cur.children[idx] = new  TrieNode();
                }
                cur = cur.children[idx];
                cur.wordList.add(words[i]);
            }
        }
        return root;
    }

    class TrieNode{
        TrieNode[] children;
        List<String> wordList;
        public TrieNode(){
            children = new TrieNode[26];
            wordList = new ArrayList<>();
        }
        public List<String> findWords(String prefix){
           List<String> ans = new ArrayList<>();
           List<TrieNode> candidates = new ArrayList<>();
           candidates.add(root);
           int n  = prefix.length();
           for(int i = 0; i < n; i++){
               int t = prefix.charAt(i) - 'a';
               int size = candidates.size();
               for(int j = 0; j < size; j++){
                   TrieNode node = candidates.remove(0);
                   if(node.children[t]!=null){
                       candidates.add(node.children[t]);
                   }
               }
           }
           for(TrieNode node: candidates){
               ans.addAll(node.wordList);
           }
           return ans;
        }
    }
}

3. Word Break II

s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

public List<String> wordBreak(String s, Set<String> wordDict) {
    return DFS(s, wordDict, new HashMap<String, LinkedList<String>>());
}       

// DFS function returns an array including all substrings derived from s.
List<String> DFS(String s, Set<String> wordDict, HashMap<String, LinkedList<String>>map) {
    if (map.containsKey(s)) 
        return map.get(s);
        
    LinkedList<String>res = new LinkedList<String>();     
    if (s.length() == 0) {
        res.add("");
        return res;
    }               
    for (String word : wordDict) {
        if (s.startsWith(word)) {
            List<String>sublist = DFS(s.substring(word.length()), wordDict, map);
            for (String sub : sublist) 
                res.add(word + (sub.isEmpty() ? "" : " ") + sub);               
        }
    }       
    map.put(s, res);
    return res;
}

DP:

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        int n = s.length();
        if(n == 0)  return new ArrayList<String>();
        List<String>[] dp = new ArrayList[n+1];
        for(int i = 0; i <= n; i++)
            dp[i] =new ArrayList<String>();
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++)
                if(wordDict.contains(s.substring(j,i))){
                    if(j == 0) dp[i].add(s.substring(j,i));
                    else if(dp[j].size()!=0){
                        for(int k = 0; k < dp[j].size(); k++){
                            String str = dp[j].get(k);
                            str += ' '+s.substring(j,i);
                            dp[i].add(str);
                        }
                    }
                }
        }
        return dp[n];
    }
}

4. Wildcard Matching

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Backtracking

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        return dfs(s,p,new HashMap<>());
    }
    public boolean dfs(String s,String p,Map<String,Boolean>map){
        if(map.containsKey(s+'/'+p)) return map.get(s+'/'+p);
        if(s.length()==0&&p.length()==0) return true;
        if(p.length()==0) return false;
        if(s.length()==0){
            int i = 0;
            while(i < p.length() && p.charAt(i)=='*') i++;
            return i == p.length();
        }
        boolean ans = false;
        if(p.charAt(0) == '*'){
            ans =  dfs(s.substring(1),p,map) ||  dfs(s,p.substring(1),map) ;

        }else{
            if(p.charAt(0)=='?'||p.charAt(0)==s.charAt(0))
                ans = dfs(s.substring(1),p.substring(1),map);
        }
        map.put(s+'/'+p,ans);
        return ans;
    }
}

DP:

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean []dp = new boolean[m+1];
        dp[0] = true;
        for(int i = 1; i <= n; i++){
            // boolean[] pre = Arrays.copyOf(dp,m+1);
            boolean topLeft = dp[0];
            dp[0] = dp[0] && p.charAt(i-1) == '*';
            for(int j = 1; j <= m; j++){
                boolean top = dp[j];
                if(p.charAt(i-1)=='*'){
                    // dp[j] = pre[j]||dp[j-1];
                    dp[j] = dp[j-1] || top;
                }
                else{ 
                    // dp[j] = pre[j-1] && (p.charAt(i-1) == '?' || s.charAt(j-1)==p.charAt(i-1));
                    dp[j] = topLeft && (p.charAt(i-1) == '?' || s.charAt(j-1)==p.charAt(i-1));
                    
                }
                topLeft = top;
            }
        }
        return dp[m];
    }
}

5. Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

思路：http://bangbingsyb.blogspot.com/2014/11/leetcode-permutation-sequence.html

同样先通过举例来获得更好的理解。以n = 4，k = 9为例：

1234

1243

1324

1342

1423

1432

2134

2143

2314 <= k = 9

2341

2413

2431

3124

3142

3214

3241

3412

3421

4123

4132

4213

4231

4312

4321

最高位可以取{1, 2, 3, 4}，而每个数重复3! = 6次。所以第k=9个permutation的s[0]为{1, 2, 3, 4}中的第9/6+1 = 2个数字s[0] = 2。

而对于以2开头的6个数字而言，k = 9是其中的第k' = 9%(3!) = 3个。而剩下的数字{1, 3, 4}的重复周期为2! = 2次。所以s[1]为{1, 3, 4}中的第k'/(2!)+1 = 2个，即s[1] = 3。

对于以23开头的2个数字而言，k = 9是其中的第k'' = k'%(2!) = 1个。剩下的数字{1, 4}的重复周期为1! = 1次。所以s[2] = 1.

对于以231开头的一个数字而言，k = 9是其中的第k''' = k''/(1!)+1 = 1个。s[3] = 4

when k == 6,
the first digit: 6/6+1 = 2, but it should be 1 ==> thus k-- before we start compute

public class Solution {
    
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n+1];
        boolean[] visited = new boolean[n+1];
        factorial[0] = 1;
        int total = 0;
        for(int i = 1; i <=n; i++){
            factorial[i] = i*factorial[i-1];
            total+=factorial[i];
        }
        if(k<=0||k>total) return "";
        StringBuilder sb = new StringBuilder();
        k--;
        while(n>0){
            int pos = k/factorial[n-1]+1;
            for(int i = 1,j=0; i < visited.length; i++){
                if(!visited[i]){
                    j++;
                }
                if(j == pos){
                    visited[i] = true;
                    sb.append(i);
                    break;
                }
            }
            n--;
            k%=factorial[n];
        }
        return sb.toString();
    }
}

6. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

Backtracking:

public class Solution {
    List<List<String>> ans;
    public List<List<String>> partition(String s) {
        ans = new ArrayList<List<String>>();
        backTrack(s,0,new ArrayList<String>());
        return ans;
    }
    public void backTrack(String s, int start,ArrayList<String> list){
        if(list.size()>0 
            && start==s.length()){
                List<String> copy = (ArrayList<String>) list.clone();
                resultLst.add(copy);
        }
        for(int i = start; i<s.length(); i++){
            if(isPalindrome(s,start,i)){
                list.add(s.substring(start,i+1));
                backTrack(s,i+1,list);
                list.remove(list.size()-1);
            }
        }
    }
    public boolean isPalindrome(String s,int i, int j){
        for(; i < j; i++,j--){
            if(s.charAt(i)!=s.charAt(j)) return false;
        }
        return true;
    }
}

Backtracking with memorization

public class Solution {
    public List<List<String>> partition(String s) {
        return backTrack(s,0,new HashMap<>());
    }
    public List<List<String>>  backTrack(String s, int start,Map<String,List<List<String>>>map){
        ArrayList<List<String>> ans = new ArrayList<List<String>>();
        if(start==s.length()){
            ans.add(new ArrayList<>());
            return ans;
        }
        if(map.containsKey(s.substring(start))) 
            return map.get(s.substring(start));
        
        for(int i = start; i<s.length(); i++){
            if(isPalindrome(s,start,i)){
                List<List<String>> sublists = backTrack(s,i+1,map);
                for(List<String> list:sublists){
                    List<String> copy = new ArrayList<>(list);
                    copy.add(0,s.substring(start,i+1));
                    ans.add(copy);
                }
            }
        }
        map.put(s.substring(start),ans);
        return ans;
    }
    public boolean isPalindrome(String s,int i, int j){
        for(; i < j; i++,j--){
            if(s.charAt(i)!=s.charAt(j)) return false;
        }
        return true;
    }
}

DP:

public class Solution {
    public List<List<String>> partition(String s) {
        int len = s.length();
  List<List<String>>[] result = new List[len + 1];
  result[0] = new ArrayList<List<String>>();
  result[0].add(new ArrayList<String>());
  boolean[][] isPalindrome = new boolean[len][len];
  for (int i = 0; i < s.length(); i++) {
   result[i + 1] = new ArrayList<List<String>>();
   for (int left = 0; left <= i; left++) {
    if (s.charAt(left) == s.charAt(i) && (i-left <= 1 || isPalindrome[left + 1][i - 1])) {
     isPalindrome[left][i] = true;
     String str = s.substring(left, i + 1);
     for (List<String> pre : result[left]) {
      List<String> copy = new ArrayList<String>(pre);
      copy.add(str);
      result[i + 1].add(copy);
     }
    }
   }
  }
  return result[len];
    }
}

7.N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

public class Solution {
    public int totalNQueens(int n) {
        int[] ret = new int[1];
        dfs(0,n,ret,new HashSet<Integer>(),new HashSet<Integer>(),new HashSet<Integer>());
        return ret[0];
    }
    public void dfs(int i, int n,int[] ret,Set<Integer> cols, Set<Integer> occupiedDiags1,Set<Integer> occupiedDiags2 ){
        if(i==n) {ret[0]++;return;}
        for(int j = 0; j < n; j++){
            if(!cols.contains(j)&& !occupiedDiags1.contains(i-j)&&)&& !occupiedDiags2.contains(i+j)){
                cols.add(j);
                occupiedDiags1.add(i-j);
                occupiedDiags2.add(i+j);
                dfs(i+1,n,ret,cols,occupiedDiags1,occupiedDiags2);
                cols.remove(j);
                occupiedDiags1.remove(i-j);
                occupiedDiags2.remove(i+j);
            }
        }
    }
}

8. N-Queens

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ret = new ArrayList<>();
        dfs(0,n,ret,new ArrayList<String>(),new HashSet<Integer>(),new HashSet<Integer>(),new HashSet<Integer>());
        return ret;
    
    }
    public void dfs(int i, int n,List<List<String>> ret,List<String> list,Set<Integer> cols, Set<Integer> occupiedDiags1,Set<Integer> occupiedDiags2){
        if(i==n) {ret.add(new ArrayList<>(list));return;}
        for(int j = 0; j < n; j++){
            if(!cols.contains(j)&& !occupiedDiags1.contains(i-j) && !occupiedDiags2.contains(i+j)){
                cols.add(j);
                occupiedDiags1.add(i-j);
                occupiedDiags2.add(i+j);
                char[] charArray = new char[n];
                Arrays.fill(charArray, '.');
                charArray[j] = 'Q';
                String str = new String(charArray);
                list.add(str);
                dfs(i+1,n,ret,list,cols,occupiedDiags1,occupiedDiags2);
                list.remove(list.size()-1);
                cols.remove(j);
                occupiedDiags1.remove(i-j);
                occupiedDiags2.remove(i+j);
            }
        }
    }
}

9. Flip Game II

Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".

public class Solution {
    public boolean canWin(String s) {
        return canWinHelper(s.toCharArray());
    }
    public boolean canWinHelper(char[] ch) {
        for(int i = 0; i < ch.length-1; i++){
            if(ch[i]=='+'&&ch[i+1]=='+'){
                //flip
                ch[i] = '-';ch[i+1]='-';
                if(!canWinHelper(ch)){
                    ch[i] = '+';ch[i+1]='+';
                    return true;
                }
                ch[i] = '+';ch[i+1]='+';

            }
        }
        return false;
    }
}

10. Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads "3:25".

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

all combinations regardless of minutes and hours.

public class Solution {
    int[] times = {8,4,2,1,32,16,8,4,2,1};
    List<String> ans = new ArrayList<>();
    public List<String> readBinaryWatch(int num) {
        dfs(num,0,new int[2]);
        return ans;
    }
    public void dfs(int num, int i, int[] time){
        if(time[0] >= 12 || time[1] >= 60) return;
        if(num == 0) {
            String s = time[0] + ":" + (time[1] /10 == 0 ? "0"+time[1] : time[1]);
            ans.add(s); 
            return;
        }
        for(; i < 10; i++){
            if(i < 4){
               time[0] += times[i];

                // dfs i+1 to avoid repeat instead using visited hashset
                dfs(num - 1,i+1, time);
                time[0] -=  times[i]; 
            }
            else{
                time[1] += times[i-4];
                dfs(num - 1,i+1, time);
                time[1] -=  times[i-4];
            }
            
        }
        
    }
}

11. Android Unlock Patterns

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern:

Each pattern must connect at least m keys and at most n keys.
All the keys must be distinct.
If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
The order of keys used matters.

Explanation:

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |

Invalid move: 4 - 1 - 3 - 6
Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2
Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6
Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2
Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

Example:
Given m = 1, n = 1, return 9.

public class Solution {
    public int numberOfPatterns(int m, int n) {
        Set<Integer> visited = new HashSet<>();
        int ret = 0;
        int[][] skip = new int[10][10];
        skip[1][3] = skip[3][1] = 2;
        skip[1][7] = skip[7][1] = 4;
        skip[3][9] = skip[9][3] = 6;
        skip[7][9] = skip[9][7] = 8;
        skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
        for(int i = m ; i <=n; i++){
             ret+= 4 * dfs(visited,1,i-1,skip);
             ret+=4 * dfs(visited,2,i-1,skip);
             ret+= dfs(visited,5,i-1,skip);
        }
        return ret;
    }
    public int  dfs( Set<Integer> visited,int cur,int remain,int[][]skip){
        if(remain == 0) return 1;
        int ret= 0 ;
        visited.add(cur);
        for(int i = 1; i <= 9; i++){
            if(!visited.contains(i) && (skip[i][cur]==0||(visited.contains(skip[i][cur]))))
                ret += dfs(visited,i,remain-1,skip);
        }
        visited.remove(cur);
        return ret;
    }
}

12. Count Numbers with Unique Digits

Backtracking

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
      if(n==0) return 1;
      if(n==1) return 10;
      if(n>10) n = 10;
      boolean visited[] = new boolean[10];
      int[] ans = new int[1];
      dfs(0,n,visited,ans);
      return ans[0]+1;
    }
    public void dfs(int step,int n,boolean[] visited,int[]ans){
        if(step==n){
            return;
        }
        for(int i = 0; i <= 9; i++){
          if(visited[i]||(step==0&&i==0)) continue;
          ans[0]++;//add not only n digits but also n-1, n-2,...,1
          visited[i] = true;
          dfs(step+1,n,visited,ans);
          visited[i] = false;
      }
    }
      
}

DP:

 public int countNumbersWithUniqueDigits(int n) {
        //status: current pos, 
        if(n < 0) return 0;
        if(n==0) return 1;
        int uniqueDigits = 9;
        int availableDigits = 9;
        int ans = 10;
        while(--n>0){
            uniqueDigits*=availableDigits;
            availableDigits--;
            ans += uniqueDigits;
        }
        return ans;
    }

13. Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
       boolean[][] dp = new boolean[m+1][n+1];
       dp[0][0] = true;
       for(int i = 0 ; i <= m; i ++){
           for(int j = 1; j <= n; j++){
               if(p.charAt(j-1)=='*' && j >= 2){
                   dp[i][j] = dp[i][j-2] ||
                    (i>0 &&  dp[i-1][j] && 
                        (p.charAt(j-2)=='.' || p.charAt(j-2)==s.charAt(i-1))
                    );
               }
               else if (i > 0 && (p.charAt(j-1)=='.' || p.charAt(j-1)==s.charAt(i-1))){
                   dp[i][j] = dp[i-1][j-1];
               } 
               else dp[i][j] = false;
           }
       }
       return dp[m][n];
    }
}

14. Letter Combinations of a Phone Number

public class Solution {
    public List<String> letterCombinations(String digits) {
          LinkedList<String> ans = new LinkedList<String>();
            String[] mapping = new String[] {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            ans.add("");
            for(int i =0; i<digits.length();i++){
                int x = Character.getNumericValue(digits.charAt(i));
                int size = ans.size();
                for(int j = 0;j<size; j++){
                    String t = ans.remove();
                    for(char s : mapping[x].toCharArray())
                        ans.add(t+s);
                }
            }
            return ans;
    }
}

15. Generate Parentheses

public class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
         dfs(n,0,0,new StringBuilder());
         return ans;
    }
    public void dfs(int n, int left, int right, StringBuilder sb){
        if(left+right == 2*n){
            ans.add(sb.toString());
            return;
        }
        if(left < n){
            sb.append('(');
            dfs(n,left+1,right,sb);
            sb.deleteCharAt(sb.length()-1);
        }
        if(right < left){
            sb.append(')');
            dfs(n,left,right+1,sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

Iterative(BFS)

public class Solution {
    public List<String> generateParenthesis(int n) {
        LinkedList<StringBuilder> list = new LinkedList<>();
        list.add((new StringBuilder()).append('(').append(1));
        for(int i=1;i<2*n;i++){
            int size = list.size();
            for(int j=0; j < size; j++){
                StringBuilder sb = list.poll();
                int left = Integer.valueOf(sb.substring(i,sb.length()).toString());
                sb.delete(i,sb.length());
                if(left < n){
                    StringBuilder sb1 = new StringBuilder(sb); 
                    sb1.append('(').append(left+1);
                    list.offer(sb1);
                    
                }
                if(left>i-left){
                    StringBuilder sb2 = new StringBuilder(sb); 
                    sb2.append(')').append(left);
                    list.offer(sb2);
                }
            }
        }
        List<String> res = new ArrayList<>();
        for(StringBuilder sb: list) res.add(sb.delete(2*n,sb.length()).toString());
        return res;
    }
}

16. Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Backtracking

public class Solution {
    List<List<Integer>> ans = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        dfs(nums,new HashSet<>(),new LinkedList<>());
        return ans;
    }
    public void dfs(int[] nums,Set<Integer>visited,List<Integer>list){
        if(list.size() == nums.length){
            ans.add(new LinkedList<>(list));
            return ;
        }
        for(int num: nums){
            if(!visited.add(num))
                continue;
            list.add(num);
            dfs(nums,visited,list);
            list.remove(list.size()-1);
            visited.remove(num);
        }
    }
}

Iterative math

public class Solution {
     public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums==null || nums.length==0) return res;
        boolean[] used = new boolean[nums.length];
        List<Integer> list = new ArrayList<Integer>();
        Arrays.sort(nums);
        dfs(nums, used, list, res);
        return res;
    }

    public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
        if(list.size()==nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]) continue;
            if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
            used[i]=true;
            list.add(nums[i]);
            dfs(nums,used,list,res);
            used[i]=false;
            list.remove(list.size()-1);
        }
    }
}

17. Combination Sum

one number could been used multiple times
but there should not be duplicate sets in answer!!
use begin pointer to avoid duplicate. Eg.[2,3,7] for 0th position, if we want to start with 3, we will never go back to 2.

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans =new ArrayList<>();
        Arrays.sort(candidates);
        dfs(0, candidates,target,0,ans,new ArrayList<>());
        return ans;
    }
    public void dfs(int begin, int[] candidates, int target, int sum, List<List<Integer>> ans, List<Integer> list){
        if(sum == target){
            ans.add(new ArrayList<>(list));
            return;
        }
        if(sum > target) return;
        for(int i = begin; i < candidates.length; i++){
            sum+= candidates[i];
            list.add(candidates[i]);
            dfs(i,candidates,target,sum,ans,list);
            list.remove(list.size()-1);
            sum-=candidates[i];
        }
    }
}

18. Combination Sum II

duplicates in candidates

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans =new ArrayList<>();
        Arrays.sort(candidates);
        
        dfs(0, candidates,target,0,ans,new ArrayList<>());
        return ans;
    }
    public void dfs(int begin, int[] candidates, int target,int sum, List<List<Integer>> ans, List<Integer> list){
        if(sum == target){
            ans.add(new ArrayList<>(list));
            return;
        }
        if(sum > target) return;
        for(int i = begin; i < candidates.length; i++){
            if(i!=begin && candidates[i] == candidates[i-1]) continue;
            sum+= candidates[i];
            list.add(candidates[i]);
            dfs(i+1,candidates,target,sum,ans,list);
            list.remove(list.size()-1);
            sum-=candidates[i];
        }
    }
}

19. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int target ) {
        List<List<Integer>> ans =new ArrayList<>();
        dfs(1,k,target,0,ans,new ArrayList<>());
        return ans;
    }
    public void dfs(int begin,int k ,int target,int sum, List<List<Integer>> ans, List<Integer> list){
        if(k==0){
            if(sum == target)
                ans.add(new ArrayList<>(list));
            return;
        }
        for(int i = begin; i <= 9; i++){
            sum+= i;
            list.add(i);
            dfs(i+1,k-1,target,sum,ans,list);
            list.remove(list.size()-1);
            sum-=i;
        }
    }
}

20. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        // for(int i = 1 ;i < target+1;i++) dp[i] = Integer.MAX_VALUE;
        dp[0] = 1;
        for(int k = 0; k <= target; k++){
            for(int i = 0; i<nums.length; i++){
                if(k >= nums[i])
                    dp[k] += dp[k-nums[i]];
            }
        }
        return dp[target];
    }
}

21 Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(0,nums,ans,new ArrayList<>());
        return ans;
    }
    public void dfs(int begin, int[] nums, List<List<Integer>> ans, List<Integer> list){
        ans.add(new ArrayList<>(list));
        for(int j = begin; j < nums.length; j++){
           list.add(nums[j]);
           dfs(j+1,nums,ans,list);
           list.remove(list.size()-1);
        }
    }
}

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

22. Subsets II

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

public class Solution {
  public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        dfs(0,nums,ans,new ArrayList<>());
        return ans;
    }
    public void dfs(int begin, int[] nums, List<List<Integer>> ans, List<Integer> list){
        ans.add(new ArrayList<>(list));
        for(int j = begin; j < nums.length; j++){
           if(j!=begin&&nums[j] == nums[j-1]) continue;
           list.add(nums[j]);
           dfs(j+1,nums,ans,list);
           list.remove(list.size()-1);
        }
    }
}

23. Factor Combinations

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

You may assume that n is always positive.
Factors should be greater than 1 and less than n.

Examples:
input: 1
output:

[]

input: 37
output:

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

DFS:
16=2*8 --> 2*2*4 --> 2*2*2*2
16 = 4*4
prevent duplicate!! need to begin with current or larger

public class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> getFactors(int n) {
        helper(n,new ArrayList<>(),2);
        return ans;
    }
    public void  helper(int n,ArrayList<Integer> list,int begin){
        if(n == 1){
            if(list.size()>1)
                ans.add(new ArrayList<>(list));
        }
        for(int i = begin; i<= n;i++){
            if(n%i==0){
                list.add(i);
                helper(n/i,list,i);
                list.remove(list.size()-1);
            }
        }
    }
}

Iterative DFS(Stack):

public class Solution {
   static class Node{
        int n=0;
        int i=0;
        List<Integer> list;
        public Node(int n, int i,List<Integer> list){
            this.n = n;
            this.i = i;
            this.list = list;
            
        }
    }
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> getFactors(int m) {
        Stack<Node> stack = new Stack<>();
        stack.push(new Node(m,2,new ArrayList<>()));
        while(!stack.empty()){
            Node node = stack.pop();
            int n = node.n;
            int i = node.i;
            List<Integer> list = node.list;
            while(i<=n){
                if(n%i==0){
                    list.add(i);
                    if(i==n){
                        if(list.size()>1)
                            ans.add(new ArrayList<>(list));
                    }
                    stack.push(new Node(n/i,i,new ArrayList<>(list)));
                    list.remove(list.size()-1);
                }
                i++;
            }
        }
        return ans;
    }
}

Another Faster solution

 public List<List<Integer>> getFactors(int m) {
        Stack<Node> stack = new Stack<>();
        stack.push(new Node(m,2,new ArrayList<>()));
        while(!stack.empty()){
            Node node = stack.pop();
            int n = node.n;
            int i = node.i;
            List<Integer> list = node.list;
            while(i*i<=n){
                if(n%i==0){
                    list.add(i);
                    list.add(n/i);
                    ans.add(new ArrayList<>(list));
                    list.remove(list.size()-1);
                    stack.push(new Node(n/i,i,new ArrayList<>(list)));
                    list.remove(list.size()-1);
                }
                i++;
            }
        }
        return ans;
    }

24. Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

public class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> generatePalindromes(String s) {
        if(s.length()==0) return ans;
        Map<Character,Integer> countMap = new HashMap<>();
        int odd = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
                countMap.putIfAbsent(c,0);
                countMap.put(c,countMap.get(c)+1);
            odd += countMap.get(c) % 2 != 0 ? 1 : -1;

        }
        if(odd>1) return ans;
        char[] ch = new char[s.length()];
        if(odd == 1){
            for(Character c: countMap.keySet()){
                if(countMap.get(c)%2==1){
                    ch[s.length()/2] = c;
                    System.out.println(c);
                    break;
                }
            }
        }
        dfs(ch,s.length()-1,0,(int)s.length()/2-1,countMap);
        return ans;
    }
    
    public void dfs(char[] ch,int offset, int lo,int hi, Map<Character, Integer> countMap){
        if(lo > hi){
            ans.add(new String(ch));
        }
        for(Character c: countMap.keySet()){
            if(countMap.get(c)>1){
                ch[lo] = c;
                ch[offset-lo] = c;
                countMap.put(c,countMap.get(c)-2);
                dfs(ch,offset,lo+1,hi,countMap);
                countMap.put(c,countMap.get(c)+2);
            }
        }
    }
}

24. Sudoku Solver

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

public class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board,0,0);
    }
    public boolean dfs(char[][]board,int row, int col){
        if(col == 9){ col = 0;row++;}
        for(int i = row; i < 9; i++){
            for(int j = 0; j< 9; j++){
                if(board[i][j] == '.'){
                    for(char c = '1'; c <= '9'; c++){
                        if(isValid(board,i,j,c)){
                            board[i][j] = c;
                            if(dfs(board,i,j+1)) return true;
                            board[i][j] = '.';
                        }
                    }
                return false;
                }
            }
        }
        return true;
    }
    public boolean  isValid(char[][]board,int i,int j,char cha){
        for(int r = 0; r < 9; r++) if(board[r][j] == cha) return false;
        for(int c = 0; c < 9; c++) if(board[i][c] == cha) return false;
        for(int r =3*(i/3);r/3==i/3;r++){
            for(int c = 3*(j/3);c/3==j/3;c++)
                if(board[r][c] ==cha) return false;
        }
        return true;
    }
}

25. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

http://bangbingsyb.blogspot.com/2014/11/leetcode-gray-code.html

26. Word Ladder II

public class Solution {
        //use map to record the path, so that won't have to go  through part of the path again and again
        //1.if map record the list of path after string s,each time find a new path, 
        //need to add to all previous points
        //2.map record parent nodes, backtrace to reconstruct the full path, use this way,
        //we also need some thing to remember the steps come to this node
 public  List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        //bfs
        List<List<String>>  ans = new ArrayList<>();
        if(beginWord.length()!= endWord.length()) return ans;
        int len = endWord.length();
        wordList.add(endWord);//!important
        
        Map<String,List<String>> map = new HashMap<>();
        Map<String,Integer> ladder = new HashMap<>();
        for(String s: wordList){
         map.put(s, new ArrayList<String>());
         ladder.put(s,Integer.MAX_VALUE);
        }
        ladder.put(beginWord, 0);
        map.put(endWord, new ArrayList<String>());
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        
        int min = Integer.MAX_VALUE;
        
        while(!q.isEmpty()){
            String str = q.poll();
            int step = ladder.get(str)+1;
            if(step > min) break;    //already find the shortest
            for(char c = 'a'; c <= 'z' ;c++){
                for(int j = 0; j < len;j++){
                    StringBuilder builder = new StringBuilder(str);
                    if(c!=str.charAt(j)){
                     builder.setCharAt(j,c);
               String s=builder.toString();
               if(s.equals(endWord))min =step;
                        if(wordList.contains(s)){    //important!
                            if(step > ladder.get(s)) continue;
                            if(step < ladder.get(s)){
                             q.add(s);
                             ladder.put(s,step);
                            }
                            map.get(s).add(str);
                        } 
                    }
                }
            }
        }
        backtracking(map,beginWord,endWord,ans,new ArrayList<String>());
        return ans;
    }
    
 public void backtracking(Map<String,List<String>>map,String start,String end,List<List<String>> ans,List<String>list){
  if(end.equals(start)){
   list.add(0, start);
   ans.add(new ArrayList<>(list));
   list.remove(0);
  }else{
   for(String s: map.get(end)){
    list.add(0,end);
    backtracking(map,start,s,ans,list);
    list.remove(0);
   }
  }
 }
   
}

29. Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Examples:

pattern = "abab", str = "redblueredblue" should return true.
pattern = "aaaa", str = "asdasdasdasd" should return true.
pattern = "aabb", str = "xyzabcxzyabc" should return false.

public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        Map<Character,String> map = new HashMap<>();
        return dfs(pattern,0,str,0,map);
    }
    public boolean dfs(String pattern,int i, String str, int j,Map<Character,String> map){
        if(i == pattern.length() && j == str.length()) return true;
        if(i == pattern.length() || j == str.length()) return false;
        char key = pattern.charAt(i);
        if(map.containsKey(key)){
            String s = map.get(key);
            int n = s.length();
            if(!str.substring(j,Math.min(j+n,str.length())).equals(s)) return false;
            return dfs(pattern,i+1,str,j+n,map);
        }else{
            for(int jj = j+1; jj <= str.length(); jj++){
                String tmp = str.substring(j,jj);
                if(map.containsValue(tmp)) continue;
                map.put(key,tmp);
                if(dfs(pattern,i+1,str,jj,map))
                    return true;
                map.remove(key);
            }
        }
        return false;
    }
}

30. Restore IP Addresses

public class Solution {
    HashMap<Integer,List<String>> map = new HashMap<>();
    public List<String> restoreIpAddresses(String s) {
        return dfs(s,0,0);
    }
    public List<String> dfs(String s, int i,int step){
        List<String> ans = new ArrayList<>();
        if(i == s.length()&&step==4){
            return new ArrayList<String>(Arrays.asList(""));
        }
        if(step>=4) return ans;
        for(int j = i+1;j<=Math.min(s.length(),i+3);j++){
            String num = s.substring(i,j);
            if(j==i+1||(s.charAt(i)!='0'&&Integer.valueOf(num)<=255)){
                List<String> list = dfs(s, j,step+1);
                for(int k = 0; k < list.size(); k++){
                    String suffix = list.get(k).length()==0?"":"."+list.get(k);
                    ans.add(num+suffix);
                }
            }
        }
        return ans;
    }
}

    // c++  code
    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        string ans;
        
        for (int a=1; a<=3; a++)
        for (int b=1; b<=3; b++)
        for (int c=1; c<=3; c++)
        for (int d=1; d<=3; d++)
            if (a+b+c+d == s.length()) {
                int A = stoi(s.substr(0, a));
                int B = stoi(s.substr(a, b));
                int C = stoi(s.substr(a+b, c));
                int D = stoi(s.substr(a+b+c, d));
                if (A<=255 && B<=255 && C<=255 && D<=255)
                    if ( (ans=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3)
                        ret.push_back(ans);
            }    
        
        return ret;
    }

31. Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

public class WordDictionary {
    class TrieNode{
        public TrieNode[] children; 
        boolean isWord = false;
        public TrieNode(){
           children = new TrieNode[26]; 
        }
    }
    TrieNode root;
    // Adds a word into the data structure.
    public void addWord(String word) {
        if(root == null){
            root = new TrieNode();
        }
        TrieNode cur = root;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(cur.children[c-'a']==null){
                cur.children[c-'a'] = new TrieNode();
            }
            cur = cur.children[c-'a'];
        }
        cur.isWord = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        if(root == null) return false;
        LinkedList<TrieNode> q = new LinkedList<>();
        q.add(root);
        int i = 0;
        for(; i < word.length(); i++){
            int size = q.size();
            char c = word.charAt(i);
            while(size-- >0){
                TrieNode  cur = q.poll();

                if(c=='.'){
                    for(int j = 0; j <26; j++){
                        if(cur.children[j] != null){
                            q.add(cur.children[j]);
                        }
                    }
                }else{
                    if(cur.children[c-'a'] != null)
                        q.add(cur.children[c-'a']);
                }
            }
            if(q.isEmpty())
                return false;
        }
        while(!q.isEmpty()){
            if(q.poll().isWord)
                return true;
        }
        return false;
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

33. Generalized Abbreviation

Example:

Given word = "word", return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

public class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> generateAbbreviations(String word) {
        helper(word,0); 
        return ans;
    }
    public void helper(String word,int i){
       ans.add(word);
        for(; i <word.length(); i++){
            if(!Character.isDigit(word.charAt(i))){
                int[] ii = new int[1];
                ii[0] = i;
                helper(abbreviate(word,ii),ii[0]);
            }
        }
    }
    public String abbreviate(String s, int[] ii){
        int i = ii[0];
        int p1 = i-1;
        while(p1 >=0 && Character.isDigit(s.charAt(p1)))
            p1--;
        int num = 0;
        if(p1!=i-1)
            num=Integer.valueOf(s.substring(p1+1,i));
        num++;
        ii[0]=p1+1;
        return s.substring(0,p1+1)+ String.valueOf(num) + (i==s.length()?"":s.substring(i+1));
    }
}

The idea is: for every character, we can keep it or abbreviate it.

  public List<String> generateAbbreviations(String word){
        List<String> ret = new ArrayList<String>();
        backtrack(ret, word, 0, "", 0);

        return ret;
    }

    private void backtrack(List<String> ret, String word, int pos, String cur, int count){
        if(pos==word.length()){
            if(count > 0) cur += count;
            ret.add(cur);
        }
        else{
            backtrack(ret, word, pos + 1, cur, count + 1);
            backtrack(ret, word, pos+1, cur + (count>0 ? count : "") + word.charAt(pos), 0);
        }
    }

这道题让我们对一个单词进行部分简写，简写的规则是若干个字母可以用数字来表示，但是不能有两个相邻的数字，具体可以参考题目中给的例子，根据我以往的经验，这种列举所有情况的必定是要用DFS来写的，但是我一时半会又没想到该咋递归，后来我数了一下题目中给的例子的所有情况的个数，是16个，而word有4个字母，刚好是2的4次方，这是巧合吗，当然不是，后来我又发现如果把0到15的二进制写出来，每一个可以对应一种情况，如下所示：

0000 word
0001 wor1
0010 wo1d
0011 wo2
0100 w1rd
0101 w1r1
0110 w2d
0111 w3
1000 1ord
1001 1or1
1010 1o1d
1011 1o2
1100 2rd
1101 2r1
1110 3d
1111 4

那么我们就可以观察出规律，凡是0的地方都是原来的字母，单独的1还是1，如果是若干个1连在一起的话，就要求出1的个数，用这个数字来替换对应的字母，既然规律找出来了，那么代码就很好写了，如下所示：

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        vector<string> res;
        for (int i = 0; i < pow(2, word.size()); ++i) {
            string out = "";
            int cnt = 0, t = i;
            for (int j = 0; j < word.size(); ++j) {
                if (t & 1 == 1) {
                    ++cnt;
                    if (j == word.size() - 1) out += to_string(cnt);
                } else {
                    if (cnt != 0) {
                        out += to_string(cnt);
                        cnt = 0;
                    }
                    out += word[j];
                }
                t >>= 1;
            }
            res.push_back(out);
        }
        return res;
    }
};

34. Minimum Unique Word Abbreviation

Given a target string and a set of strings in a dictionary, find an abbreviation of this target string with the smallest possible length such that it does not conflict with abbreviations of the strings in the dictionary.

Each number or letter in the abbreviation is considered length = 1. For example, the abbreviation "a32bc" has length = 4.

Note:

In the case of multiple answers as shown in the second example below, you may return any one of them.
Assume length of target string = m, and dictionary size = n. You may assume that m ≤ 21, n ≤ 1000, and log2(n) + m ≤ 20.

Examples:

"apple", ["blade"] -> "a4" (because "5" or "4e" conflicts with "blade")

"apple", ["plain", "amber", "blade"] -> "1p3" (other valid answers include "ap3", "a3e", "2p2", "3le", "3l1").

Brooke

2016年11月25日星期五

Backtracking

8. N-Queens

没有评论:

发表评论

博客归档