Leetcode 131 Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Input: s = "a"
Output: [["a"]]

• Soruda bize bir string listesi veriliyor.Ve bu listeden oluşturulabilecek palindrome string parçalarını bulmamız isteniyor.
• Palindrome düz ve ters aynı şekilde okunabilen kelime demek.Örneğin “kaçak”.
• Bu soruyu çözmek için backtracking ile bu stringten oluşturulabilecek her harf kümesini buluruz.
• dfs çağrılıp ilk for döngüsü içine girildiğinde 3 alt küme oluşur. [a],[aa],[aab]
• Bunlardan palindrom olanları bulunur sonuç kümesine eklenir.Palindrom olmayandan devam edilmez.
• Çağrılar sonucu oluşan parçalar aşağıdaki gibidir.

[]
['a'] tüm liste dolaşılmadı
['a', 'a'] tüm liste dolaşılmadı
['a', 'a', 'b']  sonuç listesine ekle
['a', 'ab'] palindrom olmadığı için kesildi
['aa'] tüm liste dolaşılmadı
['aa', 'b']  sonuç listesine ekle
['aab'] palindrom olmadığı için kesildi

    def partition(self, s: str) -> List[List[str]]:
        res = []
        part = []
        
        def dfs(i):
            if i>= len(s): #tüm liste dolaşıldı ise ekle palindrom olmayanlar zaten i 3 olamaz.
                res.append(part.copy())
                return
            for j in range(i, len(s)):
                if self.isPali(s,i,j):
                    part.append(s[i:j+1])
                    dfs(j + 1)
                    part.pop()
                    
        dfs(0)
        return res
    
    def isPali(self, s, l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l,r = l +1, r-1
        return True