我正在尝试创建一个识别字谜的程序。下面是提示符:
如果两个字符串的字母可以重新排列以形成彼此,则这两个字符串是变位词。例如,"Eleven plus two"是"Twelve plus one"的变位词。每个字符串包含一个"v"、三个"e"、两个"l"等。编写一个程序来确定这两个字符串是否是变位词。该程序不应区分大小写,并且应忽略任何标点符号或空格。
注:
1.考虑如何将实现分解为函数。
1.注意程序的运行时间,如果每个输入字符串包含n个字符,那么高效的实现将在线性时间(即Θ(n))内运行。
我不确定我的代码是否在线性时间内运行。我应该寻找哪些东西来确保它是线性时间的?
#include<iostream>
#include<string>
using namespace std;
const char SPACE = ' ';
const char PERIOD = '.';
const char COMMA = ',';
const char A = 'A';
const char Z = 'Z';
const char a = 'a';
const char z = 'z';
void letterArray(string line, int i, int*& letterCount) {
if(line[i] >= a && line[i] <= z) {
letterCount[line[i] - a]++;
} else if (line[i] >= A && line[i] <= Z) {
letterCount[line[i] - A]++;
}
}
bool isAnagram(int*& arr1, int*& arr2) {
bool anagram = true;
for (int i = 0; i < 26; i++) {
if(arr1[i] != arr2[i]) {
anagram = false;
}
}
return anagram;
}
int main() {
string line1;
string line2;
int * letterCount1 = new int[26];
int * letterCount2 = new int[26];
getline(cin, line1);
getline(cin, line2);
for(int i = 0; i < line1.length() || i < line2.length(); i++) {
letterArray(line1, i, letterCount1);
letterArray(line2, i, letterCount2);
}
if(isAnagram(letterCount1, letterCount2) == true) {
cout<<"These two strings are anagrams."<<endl;
} else (
cout<<"These two strings are not anagrams."
);
delete[] letterCount1;
delete[] letterCount2;
}
1条答案
按热度按时间ylamdve61#
不,它不是线性的,因为每次调用这些函数-〉quadratic时,都会复制一个行字符串,使用
const std::string& line
来避免复制,那么我认为它是线性的。一些想法:
letterArray
,而不是传递数组+索引,函数对调用上下文的了解越少,它就变得越简单和通用。new
,只使用std::vector
,如果在编译时知道大小并且您关心分配,则使用std::array
。isAnagram
实际上是在测试两个数组是否相等,std::vector
可以为您使用==
执行此操作。std::equal
可以用于您现有的原始数组。line1.length() || i < line2.length()
您希望&&
在那里,否则您将超出访问范围。是的,您必须在循环后完成对较长字符串的处理。但是为什么首先将这两个调用放在单个循环中呢?它们彼此独立。我建议使用processLine
函数来构造字符计数数组并返回它。isAnagram(letterCount1, letterCount2) == true
当然你可以显式,但是因为你已经为函数选择了一个好的名字,==true
在这里是多余的。为了确保它是线性时间,我应该寻找哪些东西?
你可以像评论者说的那样测量它的执行时间,这通常是你试图优化的目标,但一般来说,你是在寻找循环和你调用的所有函数的执行时间。