Generalized Abbreviation

LintCode Q 779 - Generalized Abbreviation

Write a function to generate the generalized abbreviations of a word.(order does not matter)

Example 1:
Input word = "word", Output: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
Example 2:
Input word = "today" Output: ["1o1a1","1o1ay","1o2y","1o3","1od1y","1od2","1oda1","1oday","2d1y","2d2","2da1","2day","3a1","3ay","4y","5","t1d1y","t1d2","t1da1","t1day","t2a1","t2ay","t3y","t4","to1a1","to1ay","to2y","to3","tod1y","tod2","toda1","today"]

Solution

Use backtracking:

Our choice: use a digit or some chars to represent a word.
Our constraints: abbreviation should be valid, what is a valid abbrivation we can check Valid Word Abbreviation.
Our goal: generate abbreviations.

Code:

public List<String> generateAbbreviations(String word) {
	List<String> res = new ArrayList<String>();
	help(res, word, 0, "", 0);
	return res;
}

private void help(List<String> res, String word, int pos, String curr, int count) {
	// boundary case, our constraints
	if (pos == word.length()) {
		if (count > 0) curr = curr + count;
		res.add(curr);
	} else {
		// explore, out choice is using a number to represent a letter
		// When calling it self, the pos should + 1 and count + 1 and curr string is unchanged.
		help(res, word, pos + 1, curr, count + 1); 
		// backtrack, we need to update the curr
		if (count > 0) curr = curr + count + word.charAt(pos);
		else curr = curr + word.charAt(pos);
		// explore, our choice is using the char at that position
		// When calling it self, the pos should + 1, the count is now to be 0 and curr string is the updated one.
		help(res, word, pos + 1, curr, 0);
	}
}