JavaScript backtracking simple solution


  • 1
    D
    
    /**
     * @param {string} word
     * @return {string[]}
     */
    var generateAbbreviations = function(word) {
        
        String.prototype.replaceAt = function(index, number) {
            return this.substr(0, index) + number + this.substr(index + number);
        }
        
        let hash = {};
        let arr = [];
        
        
        for(let n = 1; n <= word.length; n++){
            for(let k = 0; k < word.length; k++){
                util(n,k,word);
            }
        }
        
        
        arr.push(word);
        return arr;
        
        
        function util(num, pos, wrd){
            
            if(wrd.length - (pos + num) < 0){
                return;
            }
            
            if(Number.isInteger(+wrd[pos - 1])){
                return;
            }
            
            let currWrd = wrd.replaceAt(pos, num);
            
            if(!hash[currWrd]){
                hash[currWrd] = true;
                arr.push(currWrd);
            }
            
            for(let n = 1; n <= wrd.length; n++){
                
                for(let k = pos + 2; k < wrd.length; k++){
                    util(n, k, currWrd);
                }
                
            }
            
        }
        
    };
    
    

Log in to reply
 

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