working code but weird python string reference problem


  • 0
    P

    Hey Guys, I encountered a weird python string operation problem and was wondering anyone could offer some insights on this problem. Basically I had this version of code first, the logic is sound but the code just wouldn't work:
    class Solution:

    def partition(self, s):
        self.res = []
        self.dfs(s, [], 0)
        return self.res
        
    def dfs(self, s, cur_sol, pos):
    
        if pos == len(s):
            self.res.append(cur_sol[:])
            return
        for i in range(pos, len(s)+1):
            palin = s[pos:i]
            if len(palin) == 0 or not self.isPalindrome(palin): 
                continue
            cur_sol.append(palin)
            self.dfs(s, cur_sol, i+1)
            cur_sol.pop()
    
    def isPalindrome(self, palin):
        size = len(palin)
        if size < 2:
            return True
        i = 0
        j = size - 1
        while i < j:
            if palin[i] != palin[j]:
                return False
            i+=1
            j-=1
        return True
    

    However if I changed the string operation in function dfs()

    def dfs(self, s, cur_sol, pos):
        if pos == len(s):
            self.res.append(cur_sol[:])
            return
        palin = ""
        for i in range(pos, len(s)):
            palin += s[i]
            if not self.isPalindrome(palin): 
                continue
            cur_sol.append(palin)
            self.dfs(s, cur_sol, i+1)
            cur_sol.pop()
    

    The program would just be working perfectly fine. I think it has to do how python handles string reference, but I'm not entirely sure what's exactly the problem.


  • 0
    P

    solved.
    The for loop in dfs needs to be modified as

    for i in range(pos, len(s)):
        palin = s[pos:i+1]
        if len(palin) == 0 or not self.isPalindrome(palin): 
            continue
        cur_sol.append(palin)
        self.dfs(s, cur_sol, i+1)
        cur_sol.pop()

Log in to reply
 

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