用 C++ 构建 K 个回文的字符串

假设我们有一个字符串 s 和一个数字 k。我们必须使用 s 中的所有字符构建 k 个非空回文字符串。所以在这里我们必须检查我们是否可以使用 s 中的所有字符来构建 k 个回文字符串。

因此，如果输入为“true”，k = 4，则输出将为 True，因为唯一可能的解决方案是将每个字符放在一个单独的字符串中。

为了解决此问题，我们将遵循以下步骤：

  • n := s 的大小

  • 如果 n < k，则 -

    • 返回 False

  • 如果 n 与 k 相同，则 -

    • 返回 True

  • 定义一个映射

  • 对于 s 中的每个字符 c

    • (将 m[c] 增加 1)

  • 奇数 := 0

  • 对于 m 中的每个键值对 it -

    • 奇数 := 奇数 + (it 的值 AND 1)

  • 奇数<＝k 时返回 True，否则返回 False

示例 

让我们看看以下实现以获得更好的理解 -

 Live Demo

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canConstruct(string s, int k) {
      int n = s.size();
      if (n < k)
         return false;
      if (n == k)
         return true;
      map<char, int> m;
      for (char c : s)
         m[c]++;
      int odd = 0;
      for (auto& it : m) {
         odd += (it.second & 1);
      }
      return odd <= k;
   }
};
main(){
   Solution ob;
   cout << (ob.canConstruct("true",4));
}

输入

"true"

输出

1

更新于：17-11-2020

164 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习
广告