Question

Formatted question description: https://leetcode.ca/all/320.html

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

 @tag-backtracking

Algorithm

If you write a binary number from 0 to 15, each binary can correspond to a situation, as shown below:

0000 word 0001 wor1 0010 wo1d 0011 wo2 0100 w1rd 0101 w1r1 0110 w2d 0111 w3 1000 1ord 1001 1or1 1010 1o1d 1011 1o2 1100 2rd 1101 2r1 1110 3d 1111 4

Then we can observe the law, wherever 0 is the original letter, and a single 1 is still 1. If there are several 1s connected together, the number of 1s is required, and this number is used to replace the corresponding letter.

Code

Java

import java.util.ArrayList;
import java.util.List;

public class Generalized_Abbreviation {

    public class Solution_iteration {
        public List<String> generateAbbreviations(String word) {
            List<String> res = new ArrayList<>();
            for (int i = 0; i < Math.pow(2, word.length()); ++i) {
                String out = "";
                int cnt = 0;
                for (int j = 0; j < word.length(); ++j) {
                    if (((i >> j) & 1) == 1) ++cnt;
                    else {
                        if (cnt != 0) {
                            out += String.valueOf(cnt);
                            cnt = 0;
                        }
                        out += word.charAt(j);
                    }
                }
                if (cnt > 0) out += String.valueOf(cnt);
                res.add(out);
            }
            return res;

        }
    }

    public class Solution {
        public List<String> generateAbbreviations(String word) {
            List<String> result = new ArrayList<>();

            result.add(word);
            dfs(0, word, result);

            return result;
        }

        private void dfs(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);
                    dfs(i + 1 + num.length(), abbr, result); // skip 1b // @note: length, since could be "123"
                }
            }
        }
    }
}

All Problems

All Solutions