Share Java backtracking and bit manipulation solution with explanation


  • 9
    M

    First solution is backtracking, idea is very simple and similar to subset2, replace 1 to word.length characters. Tricky part is when the replace length is larger then 9, the next recursion position need to add length / 10(10 is two character, 100 is three character etc..).

    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();
        help(word, 0, result);
        return result;
    }
    
    public void help(String word, int pos, List<String> result) {
        result.add(word);
        if (pos >= word.length()) {
            return;
        }
        for (int i = pos; i < word.length(); i++) {
            for (int j = 1; j + i - 1 < word.length(); j++) {
                String abbr = word.substring(0, i) + j + word.substring(j + i);
                help(abbr, i + 2 + j / 10, result);
            }
        }
    }
    

    And the bit manipulation idea is base on some previous idea, I made a few improvement and will give some explanation.

    Since we know the size of result set will be always pow(2, word.length()), so all the possible Abbreviation String can be presented as an integer(consider it in binary). In my case, 0 means the letter will not be replaced and 1 means the letter will be replaced.

    Take "word" as example, word -> 0000, 1ord -> 1000, wo2 -> 0011, 4 -> 1111 etc..

    And I use long so the word length can be longer(Although in OJ integer works, I believe no test case's word is longer than 32).

    public List<String> generateAbbreviations(String word) {
        long size = 1 << word.length();
        List<String> result = new ArrayList<>();
        for (long i = 0; i < size; i++) {
            result.add(generateString(word, i));
        }
        return result;
    }
    
    public String generateString(String word, long number) {
        StringBuilder sb = new StringBuilder();
        int consecutiveOne = 0;
        for (int i = 0; i < word.length(); i++) {
            long bit = (number >> i) & 1;
            if (bit == 1) {
                consecutiveOne++;
            } else {
                if (consecutiveOne != 0) {
                    sb.append(consecutiveOne);
                    consecutiveOne = 0;
                }
                sb.append(word.charAt(i));
            }
        }
        if (consecutiveOne != 0) {
            sb.append(consecutiveOne);
        }
        return sb.toString();
    }
    

    Please let me know if there is any more improvement.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.