时间戳

首页 > 解决方案 > 检查字符串是否为 Lapindrome

c++ - 检查字符串是否为 Lapindrome

问题描述

问题是检查给定的字符串是否是lapindrome（CodeChef）。根据问题， Lapindrome 被定义为一个字符串，当它在中间分裂时，给出两个具有相同字符和每个字符频率相同的半部分。

我尝试使用 C++ 和下面的代码解决问题

#include <iostream>
#include<cstring>
using namespace std;
bool lapindrome(char s[],int len){
     int firstHalf=0,secondHalf=0;
     char c;
     for(int i=0,j=len-1;i<j;i++,j--){
        firstHalf += int(s[i]);
        secondHalf += int(s[j]);
      }
      if(firstHalf == secondHalf){
          return true;
      }
      else
       return false;
 }

int main() {
    // your code goes here
    int t,len;
    bool result;
    char s[1000];
    cin>>t;
    while(t){
        cin>>s;
        len = strlen(s);
        result = lapindrome(s,len);
        if(result == true)
          cout<<"YES"<<endl;
        else
          cout<<"NO"<<endl;
        --t;
    }
    return 0;
}

我采用了两个计数变量，它们将存储前半部分和后半部分字符的 ascii 代码之和。然后比较这两个变量以检查两半是否相等。我已经在几个自定义输入上尝试了代码，它工作正常。但是我提交代码后，解决方案似乎是错误的。

标签： c++

解决方案

与其计算两个数组或映射中字符的频率（在输入字符串的两半中），实际上将它们计算在一个中就足够了。

为此，必须允许负计数。

示例代码：

#include <iostream>
#include <string>
#include <unordered_map>

bool isLapindrome(const std::string &text)
{
  std::unordered_map<unsigned char, int> freq;
  // iterate until index (growing from begin) and
  // 2nd index (shrinking from end) cross over
  for (size_t i = 0, j = text.size(); i < j--; ++i) {
    ++freq[(unsigned char)text[i]]; // count characters of 1st half positive
    --freq[(unsigned char)text[j]]; // count characters of 2nd half negative
  }
  // check whether positive and negative counts didn't result in 0
  // for at least one counted char
  for (const std::pair<unsigned char, int> &entry : freq) {
    if (entry.second != 0) return false;
  }
  // Otherwise, the frequencies were balanced.
  return true;
}

int main()
{
  auto check = [](const std::string &text) {
    std::cout << '\'' << text << "': "
      << (isLapindrome(text) ? "yes" : "no")
      << '\n';
  };
  check("");
  check("abaaab");
  check("gaga");
  check("abccab");
  check("rotor");
  check("xyzxy");
  check("abbaab");
}

输出：

'': yes
'abaaab': yes
'gaga': yes
'abccab': yes
'rotor': yes
'xyzxy': yes
'abbaab': no

coliru 现场演示

笔记：

关于空输入字符串，我有点不确定。如果要求不计为 Lapindrome，则需要在isLapindrome(). 这可以通过更改最终结果来实现

return true;

至

return !text.empty(); // Empty input is considered as false.

推荐阅读