320.Generalized-Abbreviation

320. Generalized Abbreviation

题目地址

https://leetcode.com/problems/generalized-abbreviation/

题目描述

Write a function to generate the generalized abbreviations of a word. 

Note: The order of the output does not matter.

Example:
Input: "word"
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

代码

Approach #1 Backtracking

Time: O(n 2^n) && Space: O(n)

class Solution {
  public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<String>();
    backtrack(ans, new StringBuilder(), word, 0, 0);
    return ans;
  }

  private void backtrack(List<String> ans, StringBuilder builder, String word, int i, int k) {
    int len = builder.length();
    if (i == word.length()) {
      if (k != 0)        builder.append(k);
      ans.add(builder.toString());
    } else {
      backtrack(ans, builder, word, i+1, k+1);

      if (k != 0)        builder.append(k);
      builder.append(word.charAt(i));
      backtrack(ans, builder, word, i+1, 0);
    }

    builder.setLength(len);  // reset builder to the original state
  }
}

Approach #2 Bit Manipulation

Time: O(n 2^n) && Space: O(n)

class Solution {
  public List<String> generateAbbreviations(String word) {
    List<String> ans = new ArrayList<>();
    for (int x = 0; x < (1 << word.length()); x++) {
      ans.add(abbr(word, x));
    }
    return ans;
  }

  private String abbr(String word, int x) {
    StringBuilder builder = new StringBuilder();
    int count = 0;
    for (int i = 0; i < word.length(); i++, x >>= 1) {
      if ((x & 1) == 0) {
        if (count != 0) {
          builder.append(k);
          count = 0;
        }
        builder.append(word.charAt(i));
      } else {
          count++;
        }
    } 
    if (k != 0)        builder.append(count);

    return builder.toString();
  }
}