ChunNote
0%

leetCode-131:Palindrome Partitioning

发表于 分类于

问题描述

给定一个字符串，要求将字符串分割成子字符串列表，且列表中每个子字符串都是回文字符串。要求将所有可能的分割结果返回。题目链接：**点我**

样例输入输出

输入：”aab”

输出：[[“a”, “a”, “b”], [“aa”, “b”]]

输入：”a”

输出：[[a]]

问题解法

解法一

循环遍历字符串，每次截取前面的子字符串，判断是否是回文串，如果是放入列表中，将后半段字符串进行下个递归计算，不是则跳过本次递归。最后待分割的字符串为空时，则将列表的字符串集合放入结果集中。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution
{
    public List<List<String>> partition(String s)
    {
        Map<String, Boolean> map = new HashMap<>();
        List<List<String>> result = new LinkedList<>();
        partition(s, map, new LinkedList<>(), result);
        return result;
    }

    private void partition(String str, Map<String, Boolean> map, List<String> current, List<List<String>> result)
    {
        if (str.length() == 0)
        {
            result.add(new LinkedList<>(current));
            return;
        }

        int len = str.length();
        for (int i = 1; i <= len; i++)
        {
            String prefix = str.substring(0, i);
            String suffix = str.substring(i);
            if (!isPalindrome(map, prefix))
            {
                continue;
            }
            current.add(prefix);
            partition(suffix, map, current, result);
            current.remove(current.size() - 1);
        }
    }

    private boolean isPalindrome(Map<String, Boolean> map, String str)
    {
        if (!map.containsKey(str))
        {
            map.put(str, isPalindrome(str));
        }

        return map.get(str);
    }

    private boolean isPalindrome(String str)
    {
        int len = str.length();
        int count = len / 2;
        for (int i = 0; i < count; i++)
        {
            if (str.charAt(i) != str.charAt(len - i - 1))
            {
                return false;
            }
        }

        return true;
    }
}

解法二

解法一耗时比较长，有 20 ms。观察解法一中，每次都截取了字符串，相对比较耗时，可以采用下标来进行标识判断，这样就避免了每次都截取字符串，可以节省时间，此种做法耗时 2 ms。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution
{
    public List<List<String>> partition(String s)
    {
        List<List<String>> result = new LinkedList<>();
        partition(s, 0, new LinkedList<>(), result);
        return result;
    }

    private void partition(String str, int index, List<String> current, List<List<String>> result)
    {
        if (index == str.length())
        {
            result.add(new LinkedList<>(current));
            return;
        }

        for (int i = index + 1; i <= str.length(); i++)
        {
            if (isPalindrome(str, index, i - 1))
            {
                current.add(str.substring(index, i));
                partition(str, i, current, result);
                current.remove(current.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String str, int start, int end)
    {
        int len = (end - start + 1) / 2;
        for (int i = 0; i < len; i++)
        {
            if (str.charAt(start + i) != str.charAt(end - i))
            {
                return false;
            }
        }

        return true;
    }
}