Palindrome Partitioning(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.

For example, given s = "aab", Return

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

思路： 使用DFS, str1 = str.substr(0, i); 取出前面下标从 0 开始到 i 结束的子串，判断str1是否满足回文字符串的要求。
如果不满足，那么就考虑substring(0, i + 1)。 如果满足，把满足的部分字符串加入list中，接着考虑后面的，切割字符串然后递归对切割后的字符串进行同样的操作。
最后当切割以后的字符串长度为0时，说明全部切割完成，这时将list加入result.

public class Solution {    public List> partition(String s) {        List> result = new ArrayList>();        List list = new ArrayList();        helper(result, list, s);        return result;    }    private void helper(List> result, List list, String s) {        if (s.length() == 0) {            result.add(new ArrayList(list));            return;        }        for (int i = 1; i <= s.length(); i++) {            if (!isPalindrome(s.substring(0,i))) {                continue;            }            list.add(s.substring(0, i));            helper(result, list, s.substring(i));            list.remove(list.size() - 1);        }    }    private boolean isPalindrome(String s) {        int i = 0, j = s.length() - 1;        while (i < j) {            if (s.charAt(i) != s.charAt(j)) {                return false;            }            i++;            j--;        }        return true;    }}

关键字：产品经理

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！