Clean and concise backtracking, JAVA


  • 1
    public class Solution {
        public List<String> generateAbbreviations(String word) {
            int len = word.length();
            List<String> result = new ArrayList<>();
            backtracking(word, "", result);
            return result;
        }
        
        public void backtracking(String remain, String pre, List<String> result) {
            int len = remain.length();
            result.add(pre + remain);
            // i indicates the length of substring you are going to abbreviate. 
            for (int i = 1; i <= len; i ++) {
                // j indicates the start position of your abbreviation.
                for (int j = 0; j <= len - i; j ++) {
                    String newPre = pre + remain.substring(0, j) + i;
                    // i + j reaches the end, add to result without going further. 
                    if (i + j == len) {
                        result.add(newPre);
                        continue;
                    }
                    // j + i + 1 indicates the start of string in the next level of backtracking.
                   // add charAt(i + j) prevent two consecutive numbers from happening in abbreviation result
                    backtracking(remain.substring(j + i + 1), newPre + remain.charAt(i + j), result);
                }
            }
        }
    }

  • 0
    C

    @Augustdoker
    I like your solution, intuitive and concise. The other solutions look cool but not readable. upvoted!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.