1

这是我的 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;
}

我的老师说我可以降低复杂性，但我不知道如何。我已经只经历了一半的字符串。有没有办法降低这个解决方案的复杂性？

4

5 回答 5

3

你可以尝试这样的事情：

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如果它是唯一的计数器，那没关系）。

于 2013-01-29T00:26:50.270 回答
1

我唯一能想到的就是存储的长度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;

除此之外，我看不出如何使它更简单或更高效。

于 2013-01-29T00:25:05.210 回答
1

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

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 建议了更好的代码，我将其重新挂起*。

于 2013-01-29T00:28:13.593 回答
0

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

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);
    }

}

此页面上的短语也是回文。它必须对那些起作用吗？如果是这样，这是一个非常简单的更改：

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);
    }

}
于 2013-01-29T00:57:54.067 回答
0

这是我的 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"));
    }
}
于 2019-04-21T12:54:31.853 回答