Write a function to generate the generalized abbreviations of a word.
Example:
Given word =
"word", return the following list (order does not matter):["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
Understand the problem:
A classic dfs + backtracking problem. A trick here is if we've already abbrivate part of a word, we must jump at least a character.
Code (Java):
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> result = new ArrayList<>();
result.add(word);
generateHelper(0, word, result);
return result;
}
private void generateHelper(int start, String s, List<String> result) {
if (start >= s.length()) {
return;
}
for (int i = start; i < s.length(); i++) {
for (int j = 1; i + j <= s.length(); j++) {
String num = Integer.toString(j);
String abbr = s.substring(0, i) + num + s.substring(i + j);
result.add(abbr);
generateHelper(i + 1 + num.length(), abbr, result); // skip 1b
}
}
}
}
Recursive solution with Swift:
ReplyDeletefunc generalizedAbbreviation(str: String) -> [String]{
var result = [String]()
var sb = String()
generalizedAbbreviationHelprt(str, start: 0, sb: &sb, result: &result)
return result
}
func generalizedAbbreviationHelprt(str: String, start: Int, inout sb: String, inout result: [String], isNumber: Bool = false){
if start >= str.characters.count {
result.append(sb)
return
}
let currentChar = str[start]
sb.append(currentChar)
generalizedAbbreviationHelprt(str, start: start+1, sb: &sb, result: &result)
sb.removeAtIndex(sb.endIndex.predecessor())
if isNumber == false {
var counter = 1
for _ in start..<str.characters.count {
sb.append(String(counter)[0])
generalizedAbbreviationHelprt(str, start: start+counter, sb: &sb, result: &result, isNumber: true)
sb.removeAtIndex(sb.endIndex.predecessor())
counter++
}
}
}