Java backtrack solution with explanation


  • 0
    F
    public class Solution {
        private List<String> r = new ArrayList<>();
        public List<String> generateAbbreviations(String word) {
            if(word==null){
                return r;
            }
            StringBuilder cur = new StringBuilder();
            doGenerate(word,0,cur,-1);
            return r;
        }
    
        // separate current string and trailing number, number==-1 means no trailing number
        private void doGenerate(String word, int i, StringBuilder cur,int number) {
            if(i==word.length()){
                if(number==-1) {
                    r.add(cur.toString());
                }else{
                    r.add(cur.toString()+String.valueOf(number));
                }
                return;
            }
            int oldLen = cur.length();
            // case one, add char itself. append the trailing number, then the char
            if(number!=-1) {
                cur.append(number);
            }
            cur.append(word.charAt(i));
            doGenerate(word,i+1,cur,-1);
            cur.delete(oldLen,cur.length());
            // case two add number, either combine with the previous number
            if(number!=-1){
                doGenerate(word,i+1,cur,number+1);
            }else{
            // case three, add the first "1" after a char
                doGenerate(word,i+1,cur,1);
            }
        }
    
        private boolean isNumber(char c) {
            return c>='0' && c<='9';
        }
    }

Log in to reply
 

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