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.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Analysis

Back tracking (DFS) problem，基本模式为：

1. 判断条件：在哪种情况下可以吧list加入result，返回
2. for 循环，变量i：
   1. 取一个subset放入list（符合一定条件）
   2. call dfs 函数，pos变量变为与i相关
   3. 把subset remove

对于这道题，用隔板的思想。pos代表从哪个字幕开始判断。循环中的i用来代表隔板的位置。

1. 判断条件：如果隔板已经到最后了，那么说明成功了，把这个list放到result里去。
2. for循环隔板位置
   1. 选择pos到i的一段substring
   2. 如果substring不是palindrome，continue
   3. 如果是palindrome，则把这个substring加入到list里去
   4. call dfs函数，新的pos是i，意思是看隔板后面的substring情况。
   5. 把现有substring从list里除去。

s="aab"
for: substring =    
"a"; pass "ab"; "a", "b" or "ab"     
"aa"; pass "b"           
"aab": not palindrome

Code

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        List<String> list = new ArrayList<String>();
        if(s.length()==0) {return result;}
        backTrack(list, result, s, 0);
        return result;
    }

    private void backTrack(List<String> list, List<List<String>> result, String s, int pos){
        if(pos == s.length()) {
            result.add(new ArrayList<String>(list));
            return;
        }

        for(int i=pos+1; i<=s.length(); i++){
            String substr = s.substring(pos, i);
            if(!isPalindrome(substr)){continue;}
            list.add(substr);
            backTrack(list, result, s, i);
            list.remove(list.size()-1);
        }

    }

    private boolean isPalindrome(String s){
        //note empty string cannot be put in the result in this question, so it is regarded as not palindrome
        if (s==null || s.isEmpty()) {return false;}
        int n = s.length();
        for(int i=0; i<n/2; i++){
            if (s.charAt(i)!=s.charAt(n-1-i)) {return false;}
        }
        return true;
    }
}

Notes

1. string.substring(start, end): 包括start指向的char，不包括end指向的char

Reference

Ref1