LeetCode刷题-回文排列

前言说明

算法学习，日常刷题记录。

题目连接

回文排列

题目内容

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语，排列是指字母的重新排列。

回文串不一定是字典当中的单词。

示例1:

输入："tactcoa"

输出：true(排列有"tacocat"、"atcocta"，等等)

分析过程

分析思路

发现成对的字符消掉，如果有单个的字符，统计其出现的次数，如果字符串的长度为偶数个，出现了单个类型的字符就不能构成回文串了，如果字符串的长度是奇数个，只能出现一个单个类型的字符，否则就不能构成回文串了。

当字符串长度为偶数时，如果到最后能消掉所有成对的字符，那么能构成回文串。

当字符串长度为奇数时，如果只发现一个单个类型的字符，并且到最后能消掉所有成对的字符，那么能构成回文串。

解答过程

先定义单个字符出现次数的变量为singleTime，初始化为0。

所以循环判断字符串s的长度是否大于0，每次循环过程中，获取字符串第一个字符c，再通过indexOf方法获取字符串出现字符c的第一个索引i，再通过substring方法获取去掉第一个字符c后的字符串，再通过indexOf方法获取出现字符c的第二个索引n。

如果第二个索引n大于-1，那么存在第二个索引n，字符c是成对的，再通过substring方法获取去掉两个字符c后的字符串。

如果第二个索引n小于等于-1，那么不存在第二个索引n，单个字符出现次数singleTime加1。

如果字符串长度为偶数，那么字符必须成对出现才能构成回文串，这时候出现单个类型的字符，不能构成回文串，返回false。

如果字符串长度奇数，必须只出现一个单个类型的字符，字符串才有可能构成回文串，如果singleTime不等于1，返回false。

最后，若能循环结束，证明字符串能构成回文串，返回true。

解答代码

class Solution {
    public boolean canPermutePalindrome(String s) {
        // 字符串长度
        int size = s.length();

        // 单个字符出现次数
        int singleTime = 0;

        while (s.length() > 0) {
            // 获取字符串的第一个字符
            char c = s.charAt(0);

            // 获取出现字符c的第一个索引
            int i = s.indexOf(c);

            // 获取去掉一个字符c后的字符串
            s = s.substring(0, i) + s.substring(i + 1);

            // 获取出现字符c的第二个索引
            int n = s.indexOf(c);

            if (n > -1) {
                // 若存在第二个字符c，获取去掉两个字符c后的字符串
                s = s.substring(0, n) + s.substring(n + 1);
            } else {
                // 若不存在第二个字符c，单个字符出现次数自增1
                ++singleTime;

                if (size % 2 == 0) {
                    // 若字符串长度为偶数，字符必须成对出现才能构成回文串
                    return false;
                } else {
                    // 若字符串长度为奇数，必须要出现一个单独的字符
                    if (singleTime != 1) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}

提交结果

执行用时3ms，时间击败7.46%的用户，内存消耗38.8MB，空间击败5.12%的用户。

运行结果

运行时间和运行空间不是很理想，还有待优化。

关注更多

更多链接：更多链接