Java backtracking solution


  • 174
    S

    The idea is: for every character, we can keep it or abbreviate it. To keep it, we add it to the current solution and carry on backtracking. To abbreviate it, we omit it in the current solution, but increment the count, which indicates how many characters have we abbreviated. When we reach the end or need to put a character in the current solution, and count is bigger than zero, we add the number into the solution.

      public List<String> generateAbbreviations(String word){
            List<String> ret = new ArrayList<String>();
            backtrack(ret, word, 0, "", 0);
    
            return ret;
        }
    
        private void backtrack(List<String> ret, String word, int pos, String cur, int count){
            if(pos==word.length()){
                if(count > 0) cur += count;
                ret.add(cur);
            }
            else{
                backtrack(ret, word, pos + 1, cur, count + 1);
                backtrack(ret, word, pos+1, cur + (count>0 ? count : "") + word.charAt(pos), 0);
            }
        }

  • 0
    Y

    Amazing! Elegant Solution!


  • 2
    A

    What is the time complexity of this solution? O(2^n) ?


  • -2
    C

    It should be O(n!), as far as I am concern.


  • 0

    clearly O(2^n)


  • 0

    I love your solution!


  • 0
    L

    really neat solution!


  • 6
    2

    Here is my C++ implementation of your solution

    class Solution {
    public:
        vector<string> generateAbbreviations(string word) {
            vector<string> result;
            dfs(result, word, 0, 0, "");
            return result;
        }
        
        void dfs(vector<string>& result, string word, int pos, int count, string cur) {
            if(pos == word.size()) {
                if(count > 0)   cur += to_string(count);
                result.push_back(cur);
                return;
            }
            /** add the current word **/
            if(count > 0) {
                dfs(result, word, pos + 1, 0, cur + to_string(count) + word[pos]);
            } 
            else {
                dfs(result, word, pos + 1, 0, cur + word[pos]);
            }
            /** skip the current word **/
            dfs(result, word, pos + 1, count + 1, cur);
            
        }
    };

  • 0
    S

    C++ implementation

    class Solution {
        void search(string&word, int pos, int count, string path, vector<string>& v){
            if(pos == word.length()) { v.push_back(path+(count? to_string(count):"")); return ; }
            search(word, pos+1, count+1, path, v);
            search(word, pos+1, 0, path+(count? to_string(count):"")+word[pos], v);
        }
    public:
        vector<string> generateAbbreviations(string word) {
            vector<string> v;
            search(word, 0, 0, "", v);
            return v;
        }
    };
    

  • 1
    T

    Amazing and easy understood!
    This is definitely O(2^n). It is easy to explain. Every char has two possibilities, either abbreviate it or omit it. So there are total 2^n possibilities.


  • 8

    I made two improvements in your code:
    (1) use StringBuilder rather than the concatenation of String.
    (2) use char[] to represent String rather than the original String.
    these two improvements make run time from 17ms to 14ms. Here is the code.

    public class Solution {
        public List<String> generateAbbreviations(String word) {
            List<String> res = new ArrayList<>();
            StringBuilder tmpRes = new StringBuilder();
            char[] wordArray = word.toCharArray();
            dfs(res, tmpRes, wordArray, 0, 0);
            return res;
        }
        
        private void dfs(List<String> res, StringBuilder tmpRes, char[] wordArray, int pos, int numCount) {
            if(pos == wordArray.length) {
                if(numCount > 0) tmpRes.append(numCount);
                res.add(tmpRes.toString());
                return;
            }
            
            // use number
            int len = tmpRes.length();
            dfs(res, tmpRes, wordArray, pos + 1, numCount + 1);
            tmpRes.setLength(len);              // backtracking
            
            // use character
            len = tmpRes.length();
            if(numCount > 0) {
                tmpRes.append(numCount).append(wordArray[pos]);
                dfs(res, tmpRes, wordArray, pos + 1, 0);    
            } else {
                tmpRes.append(wordArray[pos]);
                dfs(res, tmpRes, wordArray, pos + 1, 0);
            }
            tmpRes.setLength(len);              // backtracking
        }
    }
    

  • 0

    @soymuybien Wonderful solution!


  • 3
    S

    This is surely a great solution. But do you think this is backtracking? I don't see any "back" here.


  • 1
    J

    Another Java solution using StringBuilder - 15ms, beat 90%

        public List<String> generateAbbreviations(String word) {
            List<String> result = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            abbrHelper(word, 0, sb, result, 0);
            return result;
        }
        
        private void abbrHelper(String word, int index, StringBuilder sb, List<String> result, int count) {
            //base case
            if (index == word.length()) {
                int curLen = sb.length();
                if (count > 0) {
                    sb.append(count);
                }
                result.add(sb.toString());
                sb.setLength(curLen);
                return;
            }
            // at current layer, we can skip input or put all count and character to result
            // Choice 1:
            abbrHelper(word, index + 1, sb, result, count + 1);
            // Choice 2:
            int curLen = sb.length();
            if (count > 0) {
                sb.append(count);    
            }
            sb.append(word.charAt(index));
            abbrHelper(word, index + 1, sb, result, 0);
            sb.setLength(curLen);
        }
    

  • 1

    Very nice and short solution! But it is not actually backtracking, just dfs.


  • 0

    I have a question, in this solution, why don't we need to delete the last added part of the cur string? Whereas in another post in Discuss, which uses StringBuilder, that solution needs to setLength of sb at the end.

    Thanks in advance!


  • 0

    @zhugejunwei Is it because there is only one StringBuilder() during the whole process, and every time append a element on the same sb, it append after the same sb?

    And in this solution, cur string is always a new string?


  • 0
    R

    Genius!!!!!!!!!!!!!


  • 0
    S

    @xietao0221 use char[] arr actually makes the runtime slower


Log in to reply
 

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