LeetCode-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"]
  ]

很显然题目要用回溯法，回溯法入门可以看之前的博客，自己的解法方案如下：

public class PalindromePartitioning {
    boolean flag = true;
    boolean[] visit;
    Map<String, Boolean> map = new HashMap<>(); 
    public List<List<String>> partition(String s) {
        visit = new boolean[s.length()];
        List<List<String>> lists = new ArrayList<>();
        if (s != null && !s.isEmpty())
            partitionString(lists, s, 1);
        return lists;
    }
    public void partitionString(List<List<String>> lists, String s, int depth) {
        if (depth == s.length()) {
            List<String> list = new ArrayList<>();
            int pre = 0, i = 0;
            for (; i < s.length(); i++) {
                if (visit[i]) {
                    String sub = s.substring(pre, i);
                    if (!isPal(sub)) {
                        return;
                    }
                    list.add(sub);
                    pre = i;
                }
            }
            if (pre == 0) {
                if (!isPal(s)) {
                    return;
                }
                list.add(s);
            } else {
                String sub = s.substring(pre, i);
                if (!isPal(sub)) {
                    return;
                }
                list.add(sub);
            }
            lists.add(list);
            return;
        } 
           visit[depth] = true;
           if (pruning(s, depth)) {
               partitionString(lists, s, depth+1);
           }
           visit[depth] = false;
           partitionString(lists, s, depth+1);
    }
    public boolean pruning(String s, int depth) {
        int i = depth-1;
        while (i > 0) {
            if (visit[i] == true) {
                break;
            }
            i--;
        }
        String sub = s.substring(i, depth);
        return isPal(sub);
    }
    public boolean isPal(String sub) {
        if (map.get(sub) == null || map.get(sub) == false) {
            boolean isPal = isPalindrome(sub);
            map.put(sub, isPal);
            if (!isPal) {
                return false;
            }
        }
        return true;
    }
    public boolean isPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return false;
        }
        int i = 0, j = s.length()-1;
        while (i < j) {
            if (Character.toLowerCase(s.charAt(i++)) != Character.toLowerCase(s.charAt(j--)))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        String s = "efeef";
        PalindromePartitioning pp = new PalindromePartitioning();
        System.out.println(pp.partition(s));
    }
}

首先本题跟之前求解一个集合的子集很像，或者说回溯的题都很像。在实现这个题目之前，最好能把一个字符串的所有字串的划分实现了。之后可以再此基础上修改，本题提交了开始提交的两次都超时了。看了上面的代码也很长，都是优化过的：

1）首先第一个优化是不要每次都去判断一个字符串是否是回文，把判断过的放进一个map中，是回文value值就标记为true，否则为false；下次先查找此map，如果有就直接返回，否则，调用isPalindrome(String s)方法进行判断，并且加入map中。这个优化的目的，因为字串的重复还是比较多的，不知道这个优化效率提升多少

2）第二个优化是用的剪枝的思想，方法pruning(String s, int depth)实现了这个功能，判断刚加进入的字串是否回文，不是的话，直接返回，就不用在尝试下面的字串了。

但是运行时间还是很长，460ms！

好，再次上个代码，更简洁的：

public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        if (s == null || s.length() == 0) {
            return result;
        }
        ArrayList<String> partition = new ArrayList<String>();
        addPalindrome(s, 0, partition, result);
        return result;
    }
    private void addPalindrome(String s, int start, ArrayList<String> partition,
            ArrayList<ArrayList<String>> result) {
        if (start == s.length()) {
            ArrayList<String> temp = new ArrayList<String>(partition);
            result.add(temp);
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            String str = s.substring(start, i);
            if (isPalindrome(str)) {
                partition.add(str);
                addPalindrome(s, i, partition, result);
                partition.remove(partition.size() - 1);
            }
        }
    }
    private boolean isPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return false;
        }
        int i = 0, j = s.length()-1;
        while (i < j) {
            if (Character.toLowerCase(s.charAt(i++)) != Character.toLowerCase(s.charAt(j--)))
                return false;
        }
        return true;
    }

这个代码没有使用位向量的方式，这一般就是回溯法的两种方式，都在这里呈现了，这个效率要比之前那个更高。但是发现效率跟其他人比还不是很快，难道还有其他好的解法？好吧，看到我的第一程序用Map优化的方式根本就很长，明显用DP啊。

首先需要递归的填写一张表，这张表存储各个字串是否为回文，比如pair[i][j]=true表示sub(i,j)(包括边界i和j)是回文字串，所以可以写出一个递归的解：

if (i == j) pair[i][j]=true（此时为单个字符）

if (i != j) (此时为多个字符) then 需要考虑最后一个字符是否和第一字符相等，即s(i) == s(j)，则pair[i][j] = pair[i+1][j-1]，显然此时要保证i+1>= j-1

所以有第三种情况，i == j-1时，pair[i][j]=true(此时为两个字符，只需这个字符比较即可，不需要递归调用)。显然，如果s(i) != s(j)那么，pair[i][j]=false；所以在O(n^2)的复杂度下，可以把这张表填完，代码示例如下：

for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (j == i)
                    pair[j][i] = true;
                else {
                    if (s.charAt(j) != s.charAt(i))
                        continue;
                    if (j == i - 1)
                        pair[j][i] = true;
                    else
                        pair[j][i] = pair[j + 1][i - 1];
                }
            }
        }

接下来就需要，根据这张表，快速找到符合条件的字串，下面这种事DP+DFS(249ms):

public List<List<String>> partition(String s) {
        List<List<String>> lists = new ArrayList<>();
        boolean[][] pair = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (j == i)
                    pair[j][i] = true;
                else {
                    if (s.charAt(j) != s.charAt(i))
                        continue;
                    if (j == i - 1)
                        pair[j][i] = true;
                    else
                        pair[j][i] = pair[j + 1][i - 1];
                }
            }
        }
        List<String> partition = new ArrayList<>();
        addPalindrome(s, 0, partition, lists, pair);
        return lists;
    }
    private void addPalindrome(String s, int start, List<String> partition,
            List<List<String>> result, boolean[][] pair) {
        if (start == s.length()) {
            ArrayList<String> temp = new ArrayList<String>(partition);
            result.add(temp);
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            if (pair[start][i-1]) {
                String str = s.substring(start, i);
                partition.add(str);
                addPalindrome(s, i, partition, result, pair);
                partition.remove(partition.size() - 1);
            }
        }
    }

复杂度是多少O(n^2) OR O(2^n)

在思考下，根据DP的思想，在生成pair[][]的时候，其实我们已经知道怎么组装字符串了，为什么还用回溯，上代码：

public List<List<String>> partition(String s) {
        @SuppressWarnings("unchecked")
        List<List<String>>[] lists = new List[s.length()+1];
        lists[0] = new ArrayList<List<String>>();
        lists[0].add(new ArrayList<String>());
        boolean[][] pair = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            lists[i+1] = new ArrayList<List<String>>();
            for (int j = 0; j <= i; j++) {
                if (j == i) 
                    pair[j][i] = true;
                else {
                    if (s.charAt(j) != s.charAt(i))
                        continue;
                    if (j == i - 1)
                        pair[j][i] = true;
                    else
                        pair[j][i] = pair[j + 1][i - 1];
                }
                if (pair[j][i]) {
                    String str = s.substring(j, i+1);
                    for (List<String> r : lists[j]) {
                        List<String> ri = new ArrayList<>(r);
                        ri.add(str);
                        lists[i+1].add(ri);
                    }
                }
            }
        }
        return lists[s.length()];
    }

但是这个是O(n^2)??????