Python 124ms DFS Solution


  • 0
    S

    I used DFS to solve this problem . In each loop, both 1 center case(aba) and two center case (abba) are considered. Tell me if you have any improvement suggestions! Thanks

    class Solution:
            # @param {string} s
            # @return {string[][]}
            def partition_rec(self, result, oneResult,startIndex):
                for i in range(startIndex,len(oneResult)-1):
                    // 1 center case
                    if oneResult[i] == oneResult[i+1]:
                        anotherResult = oneResult[:i]+[oneResult[i]+oneResult[i+1]]+oneResult[i+2:]
                        result += [anotherResult]
                        self.partition_rec(result, anotherResult,i)
                    // 2 center case
                    if i>0 and oneResult[i-1] == oneResult[i+1]:
                        anotherResult = oneResult[:i-1]+[oneResult[i-1]+oneResult[i]+oneResult[i+1]]+oneResult[i+2:]
                        result += [anotherResult]
                        self.partition_rec(result, anotherResult,i-1)
                    
            def partition(self, s):
                if len(s) == 0:
                    return []
                result = [] 
                oneResult = []
                for i in range(len(s)):
                    oneResult += [s[i]]
                result += [oneResult]
                self.partition_rec(result, result[0], 0)
                return result

Log in to reply
 

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