Generalized Abbreviation

• medium
• tag: backtracking
• similar: word pattern

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"]

思路

• 这是Google onsite面试题, 应该在google 189题里面也提到过.
• 先是问的这个组合的大小. 如果能想到每一个字符都有2种可能性: abbr或没有abbr.
• 以"abc"举例: 有3个letter, 所以是$$2^3 = 8$$.
  • 000 -> abc -> abc
  • 001 -> ab_ -> ab1
  • 010 -> a_c -> a1c
  • 011 -> a__ -> a2
  • 100 -> _bc -> 1bc
  • 101 -> _b_ -> 1b1
  • 110 -> __c -> 2c
  • 111 -> ___ -> 3

idea 1: backtracking, 错误做法...

• 我的想法是: 套用Backtracking模版, 通过step来iterate, i可以遍历0~len-step, 当i=0的时候, append char, 否则append i(即abbr的长度).
• 但是结果却不对. 因为我在加入char的时候重复加了, 例如w2的时候, step = 3, 这样在for loop的前2个if的时候都会加入: w2d,
• 代码如下:

public List<String> generateAbbreviationsWRONG(String word) {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    helperWRONG(word, 0, word.length(), res, sb);

    return res;
  }

private void helperWRONG(String word, int step, final int MAX, List<String> result, StringBuilder path) {
    if (step == MAX) {
      result.add(path.toString());
      return;
    }
    for (int i = 0; i <= MAX-step; ++i) {
      if (i == 0) {
        path.append(word.charAt(step));
        helperWRONG(word, step+1, MAX, result, path);
        //path.deleteCharAt(path.length()-1);
      }
      else if (path.length() != 0 && path.charAt(path.length()-1) >= '0' && path.charAt(path.length()-1) <= '9') {  //path.charAt(step-1) >= '0' && path.charAt(step-1) <= '9'
        //if (path.charAt(path.length()-1) - '0' == step)  continue;
        path.append(word.charAt(step));
        helperWRONG(word, step+1, MAX, result, path);
        //path.deleteCharAt(path.length()-1);
      }
      else {
        path.append(i);
        helperWRONG(word, step+i, MAX, result, path);
        //path.deleteCharAt(path.length()-1);
      }
      path.deleteCharAt(path.length()-1);
    }
}

idea 2: Backtracking, 正确做法

• 参考的discuss: link
• 正确的做法是: 只分成2种情况: alphabet+abbr, alphabet. 原因是: path的最后一个字符是数字的话, 则只能加入alphabet; 若是字母, 则可以加入字母或数字.
• 代码如下:

private void helper(String word, int start, String path, List<String> res, boolean wasAbbr) {
    if (start == word.length()) {
        res.add(path);
        return;
    }
    if (wasAbbr == false) {
        for (int end = start + 1; end <= word.length(); ++i) {
            helper(word, end, path+Integer.toString(end-start), res, true);
        }
    }
    helper(word, start + 1, path+word.charAt(start), res, false);
}

奇怪!!!

• 34 / 49 test cases passed.
• 我照着idea2那样写, 只是还是使用stringBuilder. 结果能过34个case, 但是fail在"dictionary"?
• 很奇怪!!!
• 代码如下:

public List<String> generateAbbreviationsWRONG(String word) {
    List<String> res = new ArrayList<>();
    helperFIX(word, 0, word.length(), res, new StringBuilder(), false);

    return res;
  }

  /**
   * Why this passes for 38 tests, like "word", "abc", but failed in "dictionary"???
   */
  private void helperFIX(String word, int step, final int MAX, List<String> result, StringBuilder path, boolean preAbbr) {
    if (step == MAX) {
      result.add(path.toString());
      return;
    }
    if (!preAbbr) {
      for (int i = step + 1; i <= MAX; ++i) {
        path.append(i - step);
        helperFIX(word, i, MAX, result, path, true); //path + (i - step)
        path.deleteCharAt(path.length()-1);
      }
    }
    path.append(word.charAt(step));
    helperFIX(word, step + 1, MAX, result, path, false);  //path + (word.charAt(step))
    path.deleteCharAt(path.length()-1);
  }