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;
}
}