36ms O(2^n * n) bitmask with explanation


  • 3
    K

    There exists a one to one mapping between abbreviation words and 2 based numbers.

    Taking w2d for word as an example.

    w2d--->0110
    0110-->w11d-->w2d
    

    So to get all the abbreviations for a word, first generate all the 2 based numbers within [0, 2^n -1] then maps each 2 based number to proper abbreviation string.

    public class Solution {
        String word;
        private String generate(int mask) {
            StringBuilder ans = new StringBuilder();
            for (int i = 0; i < this.word.length(); ) {
                if ((mask &(1<<i)) == 0) {
                    ans.append(this.word.charAt(i));
                    i++;
                }
                else {
                    int cur = i;
                    while (cur < this.word.length() && ((mask & (1 << cur)) > 0)) {
                        cur++;
                    }
                    ans.append(cur - i);
                    i = cur;
                }
            }
            return ans.toString();
        }
        public List<String> generateAbbreviations(String word) {
            List<String> ans = new ArrayList<>();
            this.word = word;
            for (int mask = 0; mask < (1<<this.word.length()); mask++) {
                ans.add(generate(mask));
            }
            return ans;
        }
    }

Log in to reply
 

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