LC131. 分割回文串
class Solution {
public boolean check(List<String> v) {
for (String s : v) {
for (int i = 0; i < s.length() / 2; ++i) {
if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
return false;
}
}
}
return true;
}
public List<List<String>> partition(String s) {
int n = s.length();
List<List<String>> res = new ArrayList<List<String>>();
List<String> lst = new ArrayList<String>();
for (int i = 0; i < (1 << (n - 1)); ++i) {
lst.clear();
lst.add(String.valueOf(s.charAt(0)));
for (int j = 0; j < n - 1; ++j) {
if ((i & (1 << j)) == 0) {
lst.set(lst.size() - 1, lst.get(lst.size() - 1) + s.charAt(j + 1));
}
else {
lst.add(String.valueOf(s.charAt(j + 1)));
}
}
if (check(lst)) {
res.add(new ArrayList<String>(lst));
}
}
return res;
}
}
Post Views:
5