leetcode 336.回文对
程序员文章站
2022-07-01 17:10:11
...
原题
336.回文对
2020年8月6日 每日一题
题解
方法一 暴力法
本方法就是穷举所有前后拼接对儿，判断所得是否为回文串。
先贴出奇葩的超时代码：
//134 / 134 个通过测试用例 状态：超出时间限制
//明明示例全都过了，却显示超时，这是什么意思？
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> ans=new ArrayList<>();
for(int i=0;i<words.length;i++){
for(int j=0;j<words.length;j++){
if(i!=j&&isHuiwen(words[i]+words[j])){
List<Integer> list=new ArrayList<>();
list.add(i);
list.add(j);
ans.add(list);
}
}
}
return ans;
}
public boolean isHuiwen(String s){
for(int i=0;i<s.length()/2;i++){
if(s.charAt(i)!=s.charAt(s.length()-1-i)){
return false;
}
}
return true;
}
}
我分析可能是每个测试例都在规定的时间内完成了，可是在计算总的平均执行时间的时候，超过了规定。思忖再三，发觉是因为在字符串加减的时候花费了较多的时间，因此下面的改进版代码直接用双指针进行判断，无有实质上的拼接：
/*
@v7fgg
执行用时：664 ms, 在所有 Java 提交中击败了5.01%的用户
内存消耗：41.3 MB, 在所有 Java 提交中击败了95.24%的用户
2020年8月6日 10:01
*/
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> ans=new ArrayList<>();
for(int i=0;i<words.length;i++){
for(int j=i+1;j<words.length;j++){
if(isHuiwen(words[i],words[j])){
ans.add(Arrays.asList(i,j));
}
if(isHuiwen(words[j],words[i])){
ans.add(Arrays.asList(j,i));
}
}
}
return ans;
}
public boolean isHuiwen(String s,String t){
int i=0;
int j=t.length()-1;
while(i<s.length()&&j>=0){
if(s.charAt(i)!=t.charAt(j)){return false;}
i++;
j--;
}
if(i==s.length()){
i=0;
while(i<j){
if(t.charAt(i)!=t.charAt(j)){return false;}
i++;
j--;
}
}
else{
j=s.length()-1;
while(i<j){
if(s.charAt(i)!=s.charAt(j)){return false;}
i++;
j--;
}
}
return true;
}
}