看到一个哥们G家电面试题,求删除最少字符生成Palindrome。大神们都在讨论dp,我完全想不到。

放一个没优化的DFS。 乐神说是O(n)复杂度, 有机会的话要减少使用substring,并且要想一想能否使用memorization

private static String findPalin(String s) {
if (s.length() == 1) return s;
int lo = 0, hi = s.length() - 1;
if (s.charAt(lo) == s.charAt(hi)) {
return s.charAt(lo) + findPalin(s.substring(1, s.length() - 1)) + s.charAt(hi);
} else {
String back = findPalin(s.substring(1));
String front = findPalin(s.substring(0, s.length() - 1));
return back.length() > front.length() ? back : front;
}
}
05-04 04:37