删除最少字符生成Palindrome
2024-08-25 08:06:51
看到一个哥们G家电面试题，求删除最少字符生成Palindrome。大神们都在讨论dp，我完全想不到。
放一个没优化的DFS。 乐神说是O(n3)复杂度， 有机会的话要减少使用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;
}
}
最新文章
- NoSQL初探之人人都爱Redis：（3）使用Redis作为消息队列服务场景应用案例
- C# 热敏打印机 Socket 网络链接 打印 图片 （二）
- max server memory
- iOS基于MBProgressHUD的二次封装，一行搞定，使用超简单
- 分词工具ICTCLAS5.0使用心得
- 第二次正式java web开发项目的总结（回收站恢复）
- 配置cwrsync实现windows2008和centos7文件定时同步
- B. Pasha and String
- ural 1297(后缀数组+RMQ)
- 【转】教你爱上Blocks（闭包）
- java--ThreadPool线程池简单用法
- leetcode解析回文子串拆分
- Android的FrameLayout使用要注意的问题
- C# 10分钟完成百度人脸识别——入门篇
- 解决ajaxfileupload上传文件在IE浏览器返回data为空问题
- springboot 添加 jsp支持
- 计算kdj
- Java知多少（13）流程控制
- 内部排序->归并排序->2-路归并排序
- Unity查找子物体的方式-怎么查找GameObject