从字符串数组列表中查找最短回文的有效方法

Question

我正在尝试解决 java 中的这个问题。我有一个回文字符串数组列表。我必须从给定的数组列表中找到最短的回文字符串。我已经解决了这个问题，但正在寻找关于我的代码的反馈以及我如何尝试使代码更多 efficient/better。

这是我试过的代码。

在这种情况下，大小为 3，因为这是 最小回文串的长度。

import java.util.ArrayList;
class ShortestPalindrome {
    public static int isShortestPalindrome(ArrayList<String> list) {
        int smallest = list.get(0).length();
        boolean ret = false;
        for (String element : list) {
            ret = isPalindrome(element);
            if (ret) {
                if (element.length() < smallest) 
                    smallest = element.length();                
            }
        }
        return smallest;
    }

    private static boolean isPalindrome(String input) {
        String str = "";
        boolean result = false;

        if (input.length() == 1 || input.length() == 0)
            return true;

        if (input.charAt(0) != input.charAt(input.length() - 1))
            return false;
        StringBuilder sb = new StringBuilder(input.toLowerCase());
        str = sb.reverse().toString();
        if (input.equals(str)) {
            result = true;
        }
        return result;
    }

    public static void main(String[] args) {
        ArrayList<String> array = new ArrayList<String>();
        array.add("malayam");
        array.add("aba");
        array.add("abcdeyugugi");
        array.add("nitin");
        int size = isShortestPalindrome(array);
        System.out.println("Shortest length of string in list:" + size);
    }
}

Answer 1

下面的简单代码应该适合您。 首先检查长度，然后检查它是否实际上是回文。如果是，那就存入smallest

public static int isShortestPalindrome(ArrayList<String> list) {
    Integer smallest = null;
    for(String s:list){
        if ( (smallest == null || s.length()< smallest) && new StringBuilder(s).reverse().toString().equalsIgnoreCase(s) ){
                smallest = s.length();
        }
    }
    return smallest == null ? 0 :smallest;
}

Answer 2

这是一个流版本：

OptionalInt minimalLenOfPalindrome
            = list.paralellStream()
                    .filter(st -> {
                        StringBuilder sb = new StringBuilder(st);
                        String reversedSt = sb.reverse().toString();
                        return st.equalsIgnoreCase(reversedSt);
                    })
                    .mapToInt(String::length)
                    .min();

感谢@yassin 的回答我正在更改上面的代码：

public class SOFlow {

    private static boolean isPalindrome(String input) {

        for (int i = 0; i < input.length() / 2; ++i) {
            if (Character.toLowerCase(input.charAt(i)) != Character.toLowerCase(input.charAt(input.length() - 1 - i))) {
            return false;
            }
        }
        return true;
    }

    public static void main(String args[]) {

        List<String> list = new ArrayList<>();
        list.add("cAcc");
        list.add("a;;;;a");
        list.add("aJA");
        list.add("vrrtrrr");
        list.add("cAccccccccc");

        OptionalInt minimalLenOfPalindrome
                = list.parallelStream()
                        .filter(SOFlow::isPalindrome)
                        .mapToInt(String::length)
                        .min();

        System.out.println(minimalLenOfPalindrome);
    }
}

Answer 3

对您的代码最简单的改进是仅检查字符串是否为回文，如果它的长度小于 smallest。

顺便说一句，初始化 int smallest = list.get(0).length(); 不正确，假设第一个元素不是回文并且是所有字符串中尺寸最小的。你应该做 int smallest = Integer.MAX_VALUE;

也检查

if (input.charAt(0) != input.charAt(input.length() - 1))
            return false;

是不正确的，因为您没有将字符转换为小写（就像您稍后所做的那样），因此 "ajA" 不会是回文。

您的代码可能还有进一步的改进：

您可以通过复制和反转来替换回文检查：

for (int i = 0; i < input.length() / 2; ++i)
    if (Character.toLowerCase(input.charAt(i)) != Character.toLowerCase(input.charAt(input.length() - 1 - i)))
        return false;

这里不需要复制，在一般情况下它可能会更快（因为它可以提前终止）。

此外，就像 AKSW 提到的那样，按长度对字符串进行排序可能会更快，然后一旦找到回文就可以提前终止。

Answer 4

我对您的代码有几点意见：

总的来说 - 如果您将问题分解成更小的部分，则到处都有有效的解决方案。
正如 @AKSW 在他的评论中提到的，如果 - 在任何情况下 - 我们必须检查每个字符串的长度，最好在一开始就这样做 - 所以我们不t 运行相对昂贵的方法 isPalindrome() 与不相关的字符串。
（请注意我用排序的列表覆盖了给定的列表，即使初始化一个新的排序列表是微不足道的）
我所做的主要改进是在 isPalindrome() 方法中：
- 反转长度为 n 的字符串需要 n 时间和额外的 n space。两者比较也需要n次。
  总计：2n次，nspace
- 比较每两个匹配字符（从头到尾）需要 2 个额外的 space（对于整数）和大约 n/2次。
  总计：n/2次，2space

显然，当使用限制进行复杂度计算时，时间复杂度是相同的 - O(n) - 但第二种解决方案仍然便宜 4 倍并且成本可以忽略不计space.

因此我相信这是实现测试的最有效方法：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class ShortestPalindrome {
    public static int isShortestPalindrome(ArrayList<String> list) {
        // Sorts the given ArrayList by length
        Collections.sort(list, Comparator.comparingInt(String::length));
        for (String element : list) {
            if(isPalindrome(element)) {
                return element.length();
            }
        }
        return -1; // If there is no palindrome in the given array
    }

    private static boolean isPalindrome(String input) {
        String lowerCased = input.toLowerCase();
        int pre = 0;
        int end = lowerCased.length() - 1;
        while (end > pre) {
            if (lowerCased.charAt(pre) != lowerCased.charAt(end))
                return false;
            pre ++;
            end --;
        }
        return true;
    }

    public static void main(String[] args) {
        ArrayList<String> array = new ArrayList<>(Arrays.asList("malayam", "aba", "abcdeyugugi", "nitin"));
        int size = isShortestPalindrome(array);
        System.out.println("Shortest length of string in list: " + size);
    }
}

编辑： 我用下面的列表测试了这个算法。在检查回文之前对列表进行排序可将运行时间减少 50%。

"malayam", "aba", "abcdeyugugi", "nitin", "sadjsaudifjksdfjds", "sadjsaudifjksdfjdssadjsaudifjksdfjds", "sadjsaudifjksdfjdssadjsaudifjksdfjdssadjsaudifjksdfjds", "a"

Answer 5

使用 Java8 流，并首先考虑排序，原因与其他原因相同：

boolean isPalindrome (String input) {
    StringBuilder sb = new StringBuilder(input.toLowerCase());
    return sb == sb.reverse();
}

public static int isShortestPalindrome(ArrayList<String> list) {
    return (list.stream().sorted ((s1, s2) -> { 
        return s1.length () - s2.length (); 
    })
    .filter (s-> isPalindrome (s))
    .findFirst ()
    .map (s -> s.length ())
    .orElse (-1));
}

如果你有许多相等的、最小长度的、非常大的长度的字符串，只有在最中间是非回文的，你可能会花很多时间在 isPalindrome 上，并且更喜欢 isPalindrome1 之类的东西而不是 isPalindrome。

如果我们假设一百万个字符串的长度从 1000 到 2000 个字符均匀分布，我们最终会集中在平均上。 1000 个字符串。如果它们中的大多数除了少数字符外都是相等的，接近中间，那么微调该比较可能是相关的。但是提前找到回文会终止我们的搜索，因此回文的百分比对性能也有很大影响。

private static boolean isPalindrome1 (String s) {
    String input = s.toLowerCase (); 
    int len = input.length ();
    for (int i = 0, j = len -1; i < len/2 && j > len/2; ++i, --j)
        if (input.charAt(i) != input.charAt (j))
            return false;
    return true;
}

流排序和过滤的结果是一个选项，这是发出信号的好机会，没有找到任何东西。如果没有找到任何内容，我坚持使用 returning int 和 return -1 的接口，当然，调用者必须对其进行适当评估。

从字符串数组列表中查找最短回文的有效方法

Efficient way for finding Shortest Palindrome from Arraylist of strings

java

string

palindrome