Leetcode/G家 -- 320. Generalized Abbreviation(Backtracking)

320. Generalized Abbreviation(Backtracking)

• Difficulty: Medium

https://leetcode.com/problems/generalized-abbreviation/

Write a function to generate the generalized abbreviations of a word.

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"]

相关题： http://rainykat.blogspot.com/2017/01/leetcodef-301-remove-invalid-parentheses.html
思路： 1. When keeping char,append num(>0) and add char to solution, keep backtracking
           2. When abbreviating char, increase num and keep backtracking
DFS pattern from: https://discuss.leetcode.com/topic/32765/java-14ms-beats-100

int len = sb.length(); // decision point
... backtracking logic ...
sb.setLength(len);     // reset to decision point

Complexity: O(2^n), every char has 2 choice: abbreviate or keep
关键字： DFS(Back Tracking)

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        DFS(res, new StringBuilder(), word.toCharArray(), 0, 0);
        return res;
    }

    public void DFS(List<String> res, StringBuilder sb, char[] c, int i, int num) {
        int len = sb.length();
        if(i==c.length){
            if(num>0)sb.append(num);
            res.add(sb.toString());
        }else{
            DFS(res,sb,c,i+1,num+1);//abbr c[i], so keep backtracking
            if(num>0)sb.append(num);//not abbr c[i], so 1. add num(>0) 
            DFS(res,sb.append(c[i]),c,i+1,0);//2. appending c[i] to the solution, keep backtracking rest
        }
        sb.setLength(len);
    }
}