首页　>　文章列表　>　检查每个单词的字符是否可以重新排列以形成等差数列（AP）

检查每个单词的字符是否可以重新排列以形成等差数列（AP）

字符排列关键词：检查
289 2023-09-04

在本文中，我们将讨论如何检查给定字符串中每个单词的字符是否可以重新排列以形成等差数列（AP）。我们还将使用C++实现解决方案，并提供一个示例来说明代码的工作原理。

等差数列（AP）

等差数列（AP）是一组数字的序列，其中每个项都是通过将常数d添加到前一项来获得的。常数d被称为公差。

例如，序列 1, 3, 5, 7, 9 是一个公差为 2 的等差数列。

方法

要检查给定字符串中每个单词的字符是否可以重新排列以形成等差数列，我们将按照以下方法进行操作−

我们将把给定的字符串分割成单个单词。
对于每个单词，我们将按字母顺序对字符进行排序。
我们将计算排序单词中相邻字符的公差。
如果对于所有相邻字符对来说，公差都相同，那么单词的字符可以重新排列，形成一个等差数列。
我们将对给定字符串中的所有单词重复执行步骤2-4。
如果所有的单词可以重新排列组成一个等差数列，那么我们返回true。否则，返回false。

示例

让我们在C++中实现上述方法 -

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool canFormAP(string s) {
   vector<string> words;
   string word = "";
   for(char c : s) {
      if(c == ' ') {
         words.push_back(word);
         word = "";
      } else {
         word += c;
      }
   }
   words.push_back(word);
   for(string w : words) {
      sort(w.begin(), w.end());
      int n = w.length();
      if(n <= 2) {
         continue;
      }
      int d = w[1] - w[0];
      for(int i = 2; i < n; i++) {
         if(w[i] - w[i-1] != d) {
            return false;
         }
      }
   }
   return true;
}

int main() {
   string s = "tutorialspoint";
   if(canFormAP(s)) {
      cout << "Characters of each word can be rearranged to form an Arithmetic Progressionn";
   } else {
      cout << "Characters of each word cannot be rearranged to form an Arithmetic Progressionn";
   }
   return 0;
}

输出

Characters of each word cannot be rearranged to form an Arithmetic Progression

在上面的代码中，canFormAP函数接受一个字符串s作为输入，并返回true，如果字符串中每个单词的字符可以重新排列以形成等差数列。main函数调用canFormAP函数，将字符串"hello world"作为输入，并根据函数的返回值打印相应的消息。

示例测试用例

让我们考虑一个示例测试用例来理解上述代码的工作原理 -

string s = "the quick brown fox jumps over the lazy dog";

在这个例子中，给定的字符串是“the quick brown fox jumps over the lazy dog”。字符串中的每个单词都可以重新排列以形成一个等差数列。例如，单词“quick”可以重新排列成等差数列“cikqu”，其公差为2。正如我们所讨论的，单词“lazy”可以重新排列成等差数列“alzy”，其公差为11。

因此，在这个例子中，给定字符串中每个单词的字符可以重新排列以形成等差数列，代码的输出是"字符可以重新排列以形成等差数列"。