Leetcode 336.回文对
回文对
给定一组唯一的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例 1:
输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]]
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2:
输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]]
解释: 可拼接成的回文串为 ["battab","tabbat"]
题解：
可以合成Palindrome Pairs有几种情况:
1. ["abc", "cba"]
2. ["aabc", "cb"]
3. ["cbaa", "bc"]
要么有个当前string的reverse过来的string也存在，要么当前string的左半部分或者右半部分已经是palindrome, 剩下部分有reverse过来的string存在.
先用HashMap把原有string 和对应index保存。然后对于每一个string拆成left 和 right两个substring, 若是其中一个substring本身就是palindrom, 就看另一个substring的reverse是不是存在.
当然""也是palindrome, 所以如果左右有""存在, 那就是看left, right本身有没有对应的reverse存在.
Note: 要注意["abc", "cba"], 一个substring为""的情况只检查一遍. 不然先检查"abc", left = "", right = "abc", 或者right = "", left = "abc", reverse都存在，就会加[0,1], [1,0]. 等再检查 "cba"时 又会重复加一遍结果. 所以第二个check时要加上right.length() != 0.
Time Complexity: O(n * len), n = words.length, len时word的平均长度.
Space: O(n), regardless res.
public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(words == null || words.length < 2){
return res;
}
HashMap<String, Integer> hm = new HashMap<String, Integer>();
for(int i = 0; i<words.length; i++){
hm.put(words[i], i);
}
for(int i = 0; i<words.length; i++){
for(int j = 0; j<=words[i].length(); j++){ //j是能到word[i].length()的
String left = words[i].substring(0, j);
String right = words[i].substring(j);
if(isPalindrome(left)){
String reverseRight = new StringBuilder(right).reverse().toString();
if(hm.containsKey(reverseRight) && hm.get(reverseRight)!=i){
List<Integer> item = new ArrayList<Integer>();
item.add(hm.get(reverseRight));
item.add(i);
res.add(item);
}
}
if(isPalindrome(right)){
String reverseLeft = new StringBuilder(left).reverse().toString();
if(hm.containsKey(reverseLeft) && hm.get(reverseLeft) != i && right.length()!=0){
//Addition check is right.length() != 0
//Or will add duplicate results, like ["abc", "cba"]
List<Integer> item = new ArrayList<Integer>();
item.add(i);
item.add(hm.get(reverseLeft));
res.add(item);
}
}
}
}
return res;
}
private boolean isPalindrome(String s){
int l = 0;
int r = s.length()-1;
while(l<=r){
if(s.charAt(l++) != s.charAt(r--)){
return false;
}
}
return true;
}
}
private boolean isPalindrome(String s){
int l = 0;
int r = s.length()-1;
while(l<=r){
if(s.charAt(l++) != s.charAt(r--)){
return false;
}
}
return true;
}
}
最新文章
- Python标准库--typing
- ENode框架使用场景简述
- 简单翻译工具--必应词典第三方api使用方法
- ofbiz 本地化及邮件设置126邮箱
- CLGeocoder "Lost connection to geod" #error# when use geocodeAddressString:completionHandler
- EXTJS信息提示框的注意事项
- [terry笔记]RMAN综合学习之配置
- tomcat startup.sh提示java.lang.OutOfMemoryError: PermGen space
- JS学习笔记-OO疑问之对象创建
- CI-持续集成（2）-软件工业“流水线”技术实现（转）
- [ACM] POJ 2506 Tiling （递归，睑板）
- UML(Unified Modeling Language)同一建模语言
- MVC+Repository+UOW+EntityFrmeWork的使用
- linux通配符与正则表达式
- ORM的概念, ORM到底是什么
- web前端上传图片的几种方法
- C#实现的apache htpasswd加密
- Flutter 布局（一）- Container详解
- Iframe框架+table布局 +div布局实例
- Java Eclipse和MyEclipse快捷键