有效的回文，解决方案对于大输入大小来说太慢了

Question

我遇到了一个名为有效回文的特定leetcode问题。我的代码适用于所有测试用例，除了最后一个测试用例 479/480。

在此测试用例中，传入了一个 106890 长度的字符串，但我的代码需要很长时间才能解决它。

我决定尝试采用不同的方法，使用StringBuilder类来反转字符串，然后简单地使用reversedString.equals(originalString)来比较它们是否是回文。这种方法解决了问题并通过了所有测试用例

为什么我的双指针方法不起作用？为什么它在最后一个测试用例上失败？

这是我的解决方案(两指针)

class Solution {
public static boolean isPalindrome(String s) {
String fixedString = "";
for (char c : s.toCharArray()) {
if (Character.isDigit(c) || Character.isLetter(c)) {
fixedString += c;
}
}
fixedString = fixedString.toLowerCase();
int i = 0;
int j = fixedString.length() - 1;
System.out.println(fixedString.toCharArray());
while (i <= j) {
if (fixedString.toCharArray()[i] != fixedString.toCharArray()[j]) {
return false;
}
i += 1;
j -= 1;
}
return true;
}
}

这是我使用StringBuilder的第二个解决方案。

public class Valid_Palindrome {
public static void main(String args[]){
System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
}
public static boolean isPalindrome(String s) {
String fixedString = "";
for(char c : s.toCharArray()){
if(Character.isDigit(c) || Character.isLetter(c)){
fixedString += c;
}
}
fixedString = fixedString.toLowerCase();
StringBuilder sb = new StringBuilder(fixedString);
sb = sb.reverse();
System.out.println(sb);
return sb.toString().equals(fixedString);
}
}

从技术上讲，第二个解决方案不是应该慢得多，因为它使用的是StringBuilder吗？

如何优化我的第一个解决方案？

这是在我的 leetcode 中传递的输入字符串。

Answer 1

不要对字符串生成或反转或执行任何操作，除非迭代其字符的一半以上。

在伪代码中：

• 循环播放字符的前半部分
对于第 i
• 个字符，将其与(长度 - i - 1)第 1 个字符进行比较
• 如果不同，则返回 false
• 如果循环结束，则返回 true

Answer 2

在循环中执行字符串连接通常很慢。在第一个循环中改用StringBuilder来创建筛选的字符串。

StringBuilder sb = new StringBuilder(s.length());
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isLetterOrDigit(c))
sb.append(Character.toLowerCase(c));
}
for (int i = 0, j = sb.length() - 1; i < j; i++, j--)
if (sb.charAt(i) != sb.charAt(j))
return false;
return true;

Answer 3

代码中有几个语句可能会减慢速度。

1. fixedString += c;
   这将创建一个新的StringBuilder对象。fixedString的内容将复制到其中。然后附加字符(c)。然后将StringBuilder转换为String，并将该String分配给变量fixedString。
2. if (fixedString.toCharArray()[i] != fixedString.toCharArray()[j])
   方法toCharArray创建一个新char[]并将String的内容复制到其中。

我建议您只创建一次char[]并使用它。当然，您需要从原始字符串中删除非字母和非数字，并转换为小写。

这是我对您的 [双指针] 解决方案的重写.
(请注意，我假设空字符串或空字符串不是回文。

public static boolean isPalindrome(String s) {
if (s != null && !s.isEmpty()) {
char[] chars = s.toCharArray();
char[] temp = new char[chars.length];
int count = 0;
for (char c : chars) {
if (Character.isDigit(c) || Character.isLetter(c)) {
temp[count++] = Character.toLowerCase(c);
}
}
char[] letters = new char[count];
System.arraycopy(temp, 0, letters, 0, count);
int i = 0;
int j = count - 1;
System.out.println(letters);
while (i < j) {
if (letters[i] != letters[j]) {
return false;
}
i++;
j--;
}
return true;
}
return false;
}