Java backtracking solution


  • 0

    We can use StringBuffer to reduce space occupy and use an "stack" to record the abbreviation length.

    public List<String> generateAbbreviations(String word) {
    		List<String> results = new ArrayList<String>();
    		generate(results, word.toCharArray(), 0, 0, new StringBuffer());
    		return results;
    	}
    	
    	private void generate(List<String> results, char[] word, int index, int stack, StringBuffer result) {
    		if (index == word.length) {
    			// we have generated the word
    			int len = result.length();
    			if (stack > 0) result.append(stack);
    			results.add(result.toString());
    			result.delete(len, result.length());
    			return;
    		}
    		// no abbreviation
    		int len = result.length();
    		if (stack > 0) result.append(stack);
    		result.append(word[index]);
    		generate(results, word, index + 1, 0, result);
    		result.delete(len, result.length());
    		
    		// abbreviation
    		generate(results, word, index + 1, stack + 1, result);
    	}

Log in to reply
 

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