320. Generalized Abbreviation

二刷
用了version #1自己的思路
一个没考虑到的corner case是当sb.length() == 0的时候，不存在前一位，所以检查前一位会导致-1 index

69.68 %
class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();
        if (word == null) return result;
        helper(word, 0, new StringBuilder(), result);
        return result;
    }
    private void helper(String word, int startIndex, StringBuilder sb, List<String> result) {
        if (startIndex == word.length()) {
            result.add(sb.toString());
            return;
        }
        //keep the char
        int sbLength = sb.length();
        sb.append(word.charAt(startIndex));
        helper(word, startIndex + 1, sb, result);
        sb.setLength(sbLength);
        if (sbLength == 0 || Character.isLetter(sb.charAt(sbLength - 1))) {
            //[startIndex, endIndex]
            for (int endIndex = startIndex; endIndex < word.length(); endIndex++) {
                sb.append(endIndex + 1 - startIndex);
                helper(word, endIndex + 1, sb, result);
                sb.setLength(sbLength);
            }
        }
    }
}


Version #2 LeetCode上面的答案
Time O(2^stringLength)
Space O(stringLength) system stack
感觉逻辑更强一些
我的思路是站在当前index向后看， 这个思路相当于站在当前的index向前看

For each char c[i], either abbreviate it or not.

1. Abbreviate: count accumulate num of abbreviating chars, but don't append it yet.
2. Not Abbreviate: append accumulated num as well as current char c[i].
3. In the end append remaining num.

77.37 %
public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();
        if (word == null) return result;
        generateAbbreviationsDFSHelper (word, 0, 0, new StringBuilder(), result);
        return result;
    }
    private void generateAbbreviationsDFSHelper (String word, int currIndex, int accumulatedCount, StringBuilder path, List<String> result) {
   
        int pathOriginalLength = path.length();
        if (currIndex == word.length()) {
            if (accumulatedCount != 0) path.append(String.valueOf(accumulatedCount));
            result.add(path.toString());
        } else {
            //compress current character
            generateAbbreviationsDFSHelper (word, currIndex + 1, accumulatedCount + 1, path, result);
   
            //choose not to compress current character
            if (accumulatedCount != 0) path.append(String.valueOf(accumulatedCount));
            generateAbbreviationsDFSHelper (word, currIndex + 1, 0, path.append(word.charAt(currIndex)), result);
        }
        path.setLength(pathOriginalLength);
    }
}
Version #1 完全自己想的DFS
61.66 %
我对每一层的定义是
1、不compress当前character
2、以当前startIndex为起始点开始compress

This comes to the pattern I find powerful:

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

situation1是任意情况下都可以进行的
situation2若它的上一层是一个compressed digit的话，会出现两个连续数字的情况，如果把两个数字加在一起，则当前compressed part就不是以当前层的startIndex为起始点开始的了，违背了定义。所以需要保持一个由上一层传入的boolean prevIsDigit，只有当上一层不是digit的时候，当前层才能进行compress

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();
        if (word == null) return result;
        generateAbbreviationsDFSHelper(word, false, 0, new StringBuilder(), result);
        return result;
    }
    //Trying to compress a part of the string starts with the current index
    private void generateAbbreviationsDFSHelper(String word, boolean prevIsDigit, int startIndex, StringBuilder path, List<String> result) {
        if (startIndex == word.length()) {
            result.add(path.toString());
            return;
        }
        //Not compress
        path.append(word.charAt(startIndex));
        generateAbbreviationsDFSHelper(word, false, startIndex + 1, path, result);
        path.deleteCharAt(path.length() - 1);
        //Compress 1 to n characters
        int pathOriginalLength = path.length();
        for (int endIndex = startIndex + 1; endIndex <= word.length() && !prevIsDigit; endIndex++) {
            path.append(String.valueOf(endIndex - startIndex));
            generateAbbreviationsDFSHelper(word, true, endIndex, path, result);
            path.setLength(pathOriginalLength);
        }
    }
}