Palindrome Partition

这道题就是标准的DFS，而且不需要额外的查重，只需要判断起始点和当前点之间的字符串是不是对称就行

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        tmp, res = [], []
        self.helper(0, len(s), tmp, res, s)
        return res

    def helper(self, start, end, tmp, res, string):
        if start == end:
            ref = tmp[:]
            res.append(ref)
            return 

        for i in xrange(start, end):
            if not self.isPalindrome(string[start : i + 1]):
                continue
            tmp.append(string[start : i + 1])
            self.helper(i + 1, end, tmp, res, string)
            tmp.pop()

    def isPalindrome(self, string):
        start, end = 0, len(string) - 1
        while start < end:
            if string[start] != string[end]:
                return False
            start += 1
            end -= 1

        return True

下面是Java版本，主要用来熟悉Java的具体实现

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

    public void helper(int start, int end, List<String> tmp, List<List<String>> result, String string) {
        if (start == end) {
            ArrayList<String> ref = new ArrayList<>(tmp);
            result.add(ref);
            return;
        }

        for (int i = start; i < end; i++) {
            if (!isPalindrome(string.substring(start, i + 1))) {
                continue;
            }
            tmp.add(string.substring(start, i + 1));
            helper(i + 1, end, tmp, result, string);
            tmp.remove(tmp.size() - 1);
        }
    }

    public boolean isPalindrome(String string) {
        int start = 0;
        int end = string.length() - 1;

        while (start < end) {
            if (string.charAt(start) != string.charAt(end)) {
                return false;
            }

            start++;
            end--;
        }
        return true;
    }
}