Golang backtracking solution O(n*2^(n-1))


  • 0

    Always focus on the last string and divide it into two strings.
    At this point, if the former one is not a palindrome, we can drop the partition because in the next iteration we focus on the latter string only, so if the former one is not a palindrome, there is no chance for next iteration to create a palindrome partition.

    func partition(s string) [][]string {
    	slen := len(s)
    	if slen == 0 {
    		return [][]string{}
    	}
    
    	var res [][]string
    	if isPalindrome(s) {
    		res = append(res, []string{s})
    	}
    	doPartition(&res, []string{s})
    	return res
    }
    
    func doPartition(res *[][]string, strs []string) {
    	slen := len(strs)
    	lastStr := strs[slen-1]
    	if len(lastStr) == 1 {
    		return // no new partition can be created
    	}
    
    	for i := 0; i < len(lastStr)-1; i++ {
    		splitted0, splitted1 := lastStr[0:i+1], lastStr[i+1:]
    		if !isPalindrome(splitted0) {
    			continue
    		}
    		newStrs := make([]string, slen+1)
    		copy(newStrs[:slen-1], strs[:slen-1])
    		newStrs[slen-1], newStrs[slen] = splitted0, splitted1
    
    		if isPalindrome(splitted1) {
    			*res = append(*res, newStrs)
    		}
    		doPartition(res, newStrs)
    	}
    }
    
    func isPalindrome(s string) bool {
    	slen := len(s)
    	for i, j := 0, slen-1; i < j; i, j = i+1, j-1 {
    		if s[i] != s[j] {
    			return false
    		}
    	}
    	return true
    }
    

    We can set n-1 numbers of cut for each character, so a number of total partitions is a selection whether we insert a cut or not for those candidates, thus 2^(n-1).
    For all partition, we check its palindrome-ness so complexity is O(n*2^n)
    (copy func also takes O(n) but it's same O as the palindrome-ness check.


Log in to reply
 

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