Java 19ms, beating 92%, backtracking with StringBuilder


  • 0
    Y

    used StringBuilder to save from creating new string via concatenation

    public class Solution {
    	// DFS
    	// time complexity: O(2^n)
    	// space complexity: O(n^2), n levels of recursion, each with a O(n) substring
    	public List<String> generateAbbreviations(String word) {
    		List<String> result = new ArrayList<String>();
    		if (word == null) {
    			return result;
    		}
    		helper(word, new StringBuilder(), 0, result);
    		return result;
    	}
    
    	private void helper(String word, StringBuilder prefix, int count, List<String> result) {
    		int numDigit = numDigit(count);
    		if (word.length() == 0) {
    			if (count > 0) {
    				prefix.append(count);
    			}
    			result.add(prefix.toString());
    			if (count > 0) {
    				prefix.delete(prefix.length() - numDigit, prefix.length());
    			}
    			return;
    		}
    		// do not abbreviate the first char as a count
    		if (count > 0) {
    			prefix.append(count);
    		}
    		prefix.append(word.charAt(0));
    		helper(word.substring(1), prefix, 0, result);
    		prefix.deleteCharAt(prefix.length() - 1);
    		if (count > 0) {
    			prefix.delete(prefix.length() - numDigit, prefix.length());
    		}
    		// abbreviate the first char, and increment count
    		helper(word.substring(1), prefix, count + 1, result);
    	}
    	
    	private int numDigit(int num) {
    		int count = 1;
    		while (num > 9) {
    			count++;
    			num /= 10;
    		} 
    		return count;
    	}
    }

Log in to reply
 

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