降低isPalindrome解决方案的复杂性？

Question

这是我的isPalindrome方法

public static boolean isPalindrome(String s){
    for(int i = 0; i < s.length()/2; i++){
        int j = s.length() - 1 - i;
        if(s.charAt(i) != s.charAt(j))
            return false;
    }
    return true;
}

我的老师说我可以减少复杂性，但我看不出怎么样。我已经只通过了一半的字符串。有没有办法降低此解决方案的复杂性？

Answer 1

你可以尝试这样的事情：

public static boolean isPalindrome (String str) {
    int left = 0;
    int right = str.length() - 1;

    while (left < right) {
        if (str.charAt(left) != str.charAt(right))
            return false;
        left++;
        right--;
    }
    return true;
}

这样做的好处是每次循环都不计算右手索引，特别是因为每次都必须访问字符串长度（这是常数）。

顺便说一下，我也倾向于选择比s，i和j更有意义的变量名称 - 我的基本规则是，如果你必须依靠j，你最好更明确地命名你的计数器（i没关系如果它是唯一的柜台）。

Answer 2

我唯一能想到的就是存储s的长度：

final int n = s.length();
for(int i=0; i<n/2; i++) {
    int j = n-1-i;
    if(s.charAt(i) != s.charAt(j))
        return false;
}
return true;

除此之外，我不知道如何使它变得更简单或更有效。

Answer 3

如果他意味着代码在美学上的复杂性，那么这是一个递归的解决方案：

public static boolean isPalindrome(String s) {
    if (s.charAt(0) != s.charAt(s.length() - 1)
       return false;
    return isPalindrome(s.substring(1, s.length() - 1);
}

如果他意味着算法的复杂性，我不确定你是否可以更快地完成它。也许您可以将子串移动到不同的核心（使用线程）然后合并结果。

编辑：paxdiablo建议更好的代码，我重新编写*它。

Answer 4

如果你反转弦并且它仍然等于它自己，这意味着它是一个回文。这是我如何实现它：

package com.sandbox;

import org.apache.commons.lang.StringUtils;
import org.junit.Test;

import static junit.framework.Assert.assertFalse;
import static junit.framework.Assert.assertTrue;

public class PalindromeTest {

    @Test
    public void testTheseArePalindromes() {
        assertTrue(isPalindrome("abccba"));
        assertTrue(isPalindrome("121"));
        assertTrue(isPalindrome("Malayalam"));
        assertTrue(isPalindrome("peeweep"));
        assertTrue(isPalindrome("123 321"));
    }

    @Test
    public void testTheseAreNOTPalindromes() {
        assertFalse(isPalindrome("abc"));
        assertFalse(isPalindrome("123"));
        assertFalse(isPalindrome("123 123"));
    }

    private boolean isPalindrome(String input) {
        String lowerIn = input.toLowerCase();
        String reversed = StringUtils.reverse(lowerIn);
        return lowerIn.equals(reversed);
    }

}

The phrases on this page也是回文。是否必须对这些工作？如果是这样，这是一个非常简单的变化：

package com.sandbox;

import org.apache.commons.lang.StringUtils;
import org.junit.Test;

import static junit.framework.Assert.assertFalse;
import static junit.framework.Assert.assertTrue;

public class PalindromeTest {

    @Test
    public void testTheseArePalindromes() {
        assertTrue(isPalindrome("abccba"));
        assertTrue(isPalindrome("121"));
        assertTrue(isPalindrome("Malayalam"));
        assertTrue(isPalindrome("peeweep"));
        assertTrue(isPalindrome("123 321"));
        assertTrue(isPalindrome("A dog, a plan, a canal: pagoda."));
        assertTrue(isPalindrome("A man, a plan, a canal: Panama."));
        assertTrue(isPalindrome("A tin mug for a jar of gum, Nita."));
    }

    @Test
    public void testTheseAreNOTPalindromes() {
        assertFalse(isPalindrome("abc"));
        assertFalse(isPalindrome("123"));
        assertFalse(isPalindrome("123 123"));
    }

    private boolean isPalindrome(String input) {
        String removedPunctuation = input.toLowerCase().replaceAll("[.,;: \t]", "");
        String reversed = StringUtils.reverse(removedPunctuation);
        return removedPunctuation.equals(reversed);
    }

}

Answer 5

这是我对C＃的解决方案，我没有对它进行速度测试。

using System;

public class Palindrome
{
    public static bool IsPalindrome(string word)
    {
        var arr = word.ToCharArray();
        Array.Reverse(arr);
        return word.ToLower() == new string(arr).ToLower() ? true : false;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(Palindrome.IsPalindrome("Deleveled"));
    }
}