Another Straight Forward DFS Java Solution


  • 0
    J
        // Use DFS method. O(2^n)
        public List<String> generateAbbreviations(String word) {
            List<String> result = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            generateHelper(word, 0, sb, result, false);
            return result;
        }
        private void generateHelper(String word, int index, StringBuilder sb, List<String> result, boolean isLastDigit) {
            // base case
            if (index == word.length()) {
                result.add(sb.toString());
                return;
            }
            // At current layer, we choose to add digit or characters based on isLastDigit (if the previous position is digit.)
            // Choice 1:
            sb.append(word.charAt(index));
            generateHelper(word, index + 1, sb, result, false);
            sb.deleteCharAt(sb.length() - 1);        
            // Choice 2:
            if (!isLastDigit) {
                for (int i = 1; i <= word.length() - index; i ++) {
                    StringBuilder cur = new StringBuilder();
                    cur.append(i);
                    sb.append(cur);
                    generateHelper(word, index + i, sb, result, true);
                    sb.delete(sb.length() - cur.length(), sb.length());
                } 
            }
        }
    

Log in to reply
 

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