logo标签列表

检查一个字符串的排列是否可以成为回文串。

stringalgorithmpalindrome
8

Write a method to test if a string meets the preconditions to become a palindrome.

Eg:

Input    | Output
mmo      | True  
yakak    | True  
travel   | False
我在考虑这个方法：
  1. 为T的所有排列制作后缀树，使得T$Reverse(T)#
  2. 检查相同节点的所有排列
我有什么遗漏的吗？
你只需要对所有字符进行排列组合，并检查每个结果序列是否与其本身的反转相等。 - Adam Arold
3
你的意思是：这个字符串是否存在一个排列是回文的？ 不幸的是，标题和问题都有错误。 - Ami Tavory
3
测试结果表明你不需要进行任何排列组合，只需要进行一些审核：如果字符串长度为奇数，则应该有一个且仅有一个字符在整个字符串中出现的总次数为奇数；如果字符串长度为偶数，则所有字符在整个字符串中出现的总次数都应该是偶数。如果符合这些条件，那么你实际上正在使这个问题变得更加复杂。 - Jason Hu
所以基本上你想确定是否可以将输入字符串的字符重新排列成回文？如果是这样，那么答案是“是”，如果 1）长度为偶数，并且每个唯一字符出现了偶数次，或者 2）长度为奇数，并且每个唯一字符出现了偶数次，除了一个。 - Lasse V. Karlsen
24个回答
0

这是我的解决方案。字符串可能包含多个带有空格的单词，例如：
输入：Tact Coa 输出：true 输入：Tact Coa vvu 输出：false

public static boolean checkForPalindrome(String str) {
    String strTrimmed = str.replaceAll(" ","");
    System.out.println(strTrimmed);
    char[] str1 = strTrimmed.toCharArray();

    for (int i = 0; i < str1.length; i++) {
        str1[i] = Character.toLowerCase(str1[i]);
    }

    Arrays.sort(str1);
    String result = new String(str1);
    System.out.println(result);
    int count = 0;
    for (int j = 0; j < str1.length; j += 2) {
    if (j != str1.length-1) {
        if (str1[j] != str1[j+1]) {
            count++;
            j++;

        }
    } else {
        count++;
    }
   }        
    if (count > 1) return false;
    else return true;
}
0
此为我的解决方案。
public static void main(String[] args) {
    List<Character> characters = new ArrayList<>();
    Scanner scanner = new Scanner(System.in);
    String input = scanner.nextLine();
    for (int i = 0; i < input.length(); i++){
        char val = input.charAt(i);
        if (characters.contains(val)){
            characters.remove(characters.indexOf(val));
        } else{
            characters.add(val);
        }
    }
    if (characters.size() == 1 || characters.size() == 0){
        System.out.print("Yes");
    } else{
        System.out.print("No");
    }
}
看起来是Java，你可能会提到。看看Mureinik答案中的Edit 4 - 在我看来只是缺少一个文档注释。不要编写、发布未注释的代码！ - greybeard
0

任何字符串只有在最多一个字符出现奇数次且所有其他字符必须出现偶数次时才能成为回文。以下程序可用于检查一个字符串是否可以成为回文。

void checkPalindrome(string s)
{
vector<int> vec(256,0);    //Vector for all ASCII characters present.
for(int i=0;i<s.length();++i)
{
    vec[s[i]-'a']++;
}
int odd_count=0,flag=0;
for(int i=0;i<vec.size();++i)
{
    if(vec[i]%2!=0)
        odd_count++;
    if(odd_count>1)
    {
        flag=1;
         cout<<"Can't be palindrome"<<endl;
        break;  
    }
}
if(flag==0)
    cout<<"Yes can be palindrome"<<endl;
}
0

Python代码用于检查给定字符串是否可以形成回文：

test_str = input('enter any string = ')
count = 0 
for item in set(test_str):
    if test_str.count(item)%2 != 0:
        count+=1 
if (count>1):
    print(" palindrome cannot be formed")
else:
    print(" palindrome can be formed")

请尝试此代码，如有任何问题，请留言评论。
1
你好，欢迎来到SO！请阅读tour和如何撰写优秀答案？。那并没有回答问题。问题是一个排列是否可以成为回文。 - Tomer Shetah
0

JS解决方案：

function solution(inputString) {
  const arr = inputString.split('');
  let hasCoupleList = arr.map( (el) =>  arr.filter( (el1) => el1 == el).length % 2 == 0).filter( (el) => el == false).length;
  return (arr.length % 2 == 0)
    ? hasCoupleList == 0
    : hasCoupleList == 1;
}
0

这是我的代码：

 boolean palindromeRearranging(String inputString) {
        HashMap<Character,Integer> stCount=new HashMap<>();
        for(int i=0;i<inputString.length();i++){
            stCount.put(inputString.charAt(i),0);
        }
        for(int i=0;i<inputString.length();i++){
            int c= stCount.get(inputString.charAt(i));
            stCount.put(inputString.charAt(i),++c);
        }
        int c=0;
        for (Map.Entry<Character,Integer> entry : stCount.entrySet()){
            if(entry.getValue()%2!=0){
                c++;
                if(c>1){
                    return false;
                }
            }   
        }
        return true;
    }
你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Community
对于在字符串s中迭代“字符”，我喜欢使用for (int c: s.codepoints())。用于“计算元素”的习惯用法可能是stCount.merge(c, 1, Integer::sum)。当您不需要键时，只需迭代stCount.values()。 - greybeard
0

使用JAVA

import java.util.*;
import java.lang.*;
//Classs
class Permutation {

  /*
   *  We need to have an even number of almost all characters, 
   *  so that half can be on one side and half can be on the other side.
   *  At most one character (the middle character) can have an odd count.
   */
  public static boolean hasPalindrome(String str) {

    boolean wasOdd = false;
    for (Character c: str.toCharArray()) {

      int counter = 0;
      for (Character cc: str.toCharArray()) {
        if (c == cc) {
          counter++;
        }
      }

      if (counter % 2 == 1) {
        if (wasOdd) {
          return false;
        }
        wasOdd = true;
      }
    }


    return true;

  }
  public static void main(String args[]) throws Exception {


    //Taking string input 
    //Scanner
    Scanner s = new Scanner(System.in);
    String str = s.nextLine();
    if (Permutation.hasPalindrome(str)) {
      System.out.println("YES"); // Writing output to STDOUT

    } else {
      System.out.println("NO"); // Writing output to STDOUT


    }


  }
}

0

为什么要使用后缀树或任何其他数据结构？

回文字符串的基本要求是：所有字符的频率必须是偶数，或者只能有一个字符的频率是奇数。

示例：

输入：aabbaa

输出：a的频率为4，b的频率为2（均为偶数）

输入：xxzyzxx

输出：x的频率为4，z的频率为2，y的频率为1（只有1个奇数）

示例代码以便更好理解：

bool ispalin(string str)                      //function to check
{ 
int freq[26] = {0};               //to store frequency of character here i am
                                          // considering only lower case letters 
for (int i = 0; str.length();  i++) 
    freq[str[i]]++; 
int odd = 0; 
for (int i = 0; i < 26; i++)      //Count odd occurring characters 
{ 
    if (freq[i] & 1)                       //checking if odd
        odd++; 
    if (odd > 1)                          //if number of odd freq is greater than 1
        return false; 
}  
return true;                             //else return true
}
0

我们也可以通过集合来实现这个目标

String name = "raa";
        List<Character> temp = new ArrayList<>(name.chars()
                .mapToObj(e -> (char) e).collect(Collectors.toList()));

        for (int i = 0; i < temp.size(); i++) {
            for (int j = i + 1; j < temp.size(); j++) {
                if (temp.get(i).equals(temp.get(j))) {
                    temp.remove(j);
                    temp.remove(i);
                    i--;
                }

            }

        }

        if (temp.size() <= 1) {
            System.out.println("Pallindrome");
        } else {
            System.out.println(temp.size());
            System.out.println("Not Pallindrome");
        }
    }
0
如果我们不关心字符串中字符和空格的大小写敏感性，那么使用字典的C#示例解决方案可以如下所示：
    private static bool IsPalindromePermutation(string inputStr)
    {
        // First, check whether input string is null or whitespace.
        // If yes, then return false.
        if (string.IsNullOrWhiteSpace(inputStr))
            return false;

        var inputDict = new Dictionary<char, int>();

        // Big/small letter is not important
        var lowerInputStr = inputStr.ToLower();

        // Fill input dictionary
        // If hit a space, then skip it
        for (var i = 0; i < lowerInputStr.Length; i++)
        {
            if (lowerInputStr[i] != ' ')
            {
                if (inputDict.ContainsKey(lowerInputStr[i]))
                    inputDict[lowerInputStr[i]] += 1;
                else
                    inputDict.Add(lowerInputStr[i], 1);
            }
        }

        var countOdds = 0;
        foreach(var elem in inputDict)
        {
            if(elem.Value % 2 != 0)
                countOdds++;
        }

        return countOdds <= 1;
    }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接