时间戳

首页 > 解决方案 > 从给定的字符串中获取所有可能的回文

java - 从给定的字符串中获取所有可能的回文

问题描述

子字符串是字符串中连续的字符范围。

现在我需要找出可以重新排列的子串有多少可以形成回文。

例如：对于输入 - aabb

a
aa
aab (because after re-arranging it becomes aba)
aabb (because after re-arranging it becomes abba)
a
abb (because after re-arranging it becomes bab)
b
bb
b

So we have 9 substring palindromes.

这是我尝试过的代码：

public static int getPalindromeCount(String str) {
    // all single characters are treated as palindrome
    int count = str.length();

    // Get all sub strings
    List<String> subs = new ArrayList<>();
    subString(str, subs);

    for (String sub : subs) {
        String rev = new StringBuilder(sub).reverse().toString();

        if (rev.equals(sub)) {
            System.out.println(sub);
            count++;
        } else {
            boolean valid = isPalindrome(sub);
            System.out.println(sub + " : " + valid);
            if (valid) {
                count++;
            }
        }
    }
    return count;
}

// Check if substring can form a Palindrome
private static boolean isPalindrome(String input) {
    Set<Character> oddChars = new HashSet<>();

    for (char c : input.toCharArray()) {
        if (!oddChars.add(c)) {
            oddChars.remove(c);
        }
    }
    return oddChars.size() <= 1;
}

// Get all substrings
private static void subString(String input, List<String> list) {
    for (int i = 0; i < input.length(); i++) {
        for (int j = i + 2; j <= input.length(); j++) {
            list.add(input.substring(i, j));
        }
    }
}

isPalindrome我从这篇文章中获取的逻辑方法部分检查字符串的排列是否可以成为回文

此代码工作正常，但因超时错误而失败。

我不确定哪些输入是失败的，因为它们隐藏在我的hackerrank挑战中。

编辑：

我已经修改了我的getPalidromeCount方法来检查输入中有多少个奇数字母来决定回文数。

这是基于对这篇文章的评论：

提示：回文由所有偶数字母或所有偶数字母加上一个奇数字母（中间字符）组成。现在，您可以轻松计算可能的回文数。– vivek_23

public static int getPalindromeCount(String str) {
    List<Integer> list = new ArrayList<>(strToEvaluate.size());
    for (String str : strToEvaluate) {
        int count = str.length();

        List<String> subs = new ArrayList<>();
        subString(str, subs);
        for (String sub : subs) {
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < sub.length(); i++) {
                char c = sub.charAt(i);
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            int odds = 0;
            for (char key : map.keySet()) {
                if (map.get(key) % 2 != 0) {
                    odds++;
                    if (odds > 1) {
                        break;
                    }
                }
            }
            if (odds <= 1) {
                System.out.println(sub);
                count++;
            }

            list.add(count);
        }
    }
    return list;
}

但我仍然看到超时错误。我没有使用isPalindrome这个逻辑中的方法。

标签： javaalgorithmpalindrome

解决方案

有n(n+1)/2可能的子字符串，对于每个子字符串，您检查它是否可以重新排列，以便它在给定子字符串的长度中形成回文，O(k)让k我们考虑是否有必要分别解析每个子字符串。

暗示：

假设您有从 index to 的子字符串，您对从 index top的子字符串有k什么看法。真的有必要单独解析这个扩展子串吗？pk + 1

推荐阅读