Friday, June 10, 2016

Leetcode: 320. Generalized Abbreviation

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
            }
        }
    }
}

1 comment:

  1. Recursive solution with Swift:
    func 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++
    }
    }
    }

    ReplyDelete