Golang Bit-manipulation, Time Limit Exceeded


  • 0
    A

    Not sure what I can do to make this any faster...

    func generateAbbreviations(word string) (res []string) {
        rsbF := func(i int) int { // Return the count of contiguous set LSB's
            switch (i + 1) ^ i {
                case 1 << 1 - 1: return 0
                case 1 << 2 - 1: return 1
                case 1 << 3 - 1: return 2
                case 1 << 4 - 1: return 3
                case 1 << 5 - 1: return 4
                case 1 << 6 - 1: return 5
                case 1 << 7 - 1: return 6
                case 1 << 8 - 1: return 7
                case 1 << 9 - 1: return 8
                case 1 << 10 - 1: return 9
                case 1 << 11 - 1: return 10
                case 1 << 12 - 1: return 11
                case 1 << 13 - 1: return 12
                case 1 << 14 - 1: return 13
                case 1 << 15 - 1: return 14
                case 1 << 16 - 1: return 15
                default: panic(i)
            }
            return -1
        }
        
        for i := 0; i < (1 << uint(len(word))); i++ { // for i from 0 to 2^n-1
            thisWord := make([]byte, 0, len(word))
            rsb, k, l := 0, 0, len(word)
            for j := i; k < l; j, k = j >> 1, k + 1 {
                rsb = rsbF(j)
                if rsb > 0 { // contiguous set bits turn into an abbreviation
                    thisWord = append(thisWord, []byte(strconv.Itoa(rsb))...)
                    j >>= uint(rsb - 1)
                    k += rsb - 1
                } else {
                    if j != 0 {
                        thisWord = append(thisWord, word[k])
                    } else { // Short circuit if j == 0, just dump the rest of the word
                        thisWord, k = append(thisWord, []byte(word[k:])...), l
                    }
                }
            }
            res = append(res, string(thisWord))
        }
        return
    }

Log in to reply
 

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