Classic subset template with DFS in Java


  • 1
    T
    public class Solution {
        public List<String> generateAbbreviations(String word) {
            List<String> result = new ArrayList<String>();
            if (word.length() == 0){
                result.add("");
                return result;
            }
            helper(word, 0, false, "", result);
            return result;
        }
        public void helper(String word, int position, boolean prevNum, String temp, List<String> result){
            if (position == word.length()){
                result.add(temp);
                return;
            }
            for (int i = position; i < word.length(); i++){
                if (i == position){
                    helper(word, i + 1, false, temp + word.charAt(i), result);
                }
                if (!prevNum){
                    helper(word, i + 1, true, temp + Integer.toString(i - position + 1), result);
                }
            }
        }
    }

  • 0
    P

    Can you do some explanations? It's a great solution with classic subset backtracking algorithm. Can you explain the meaning of each parameter, such as prevNum. Thanks a lot!


Log in to reply
 

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