C++ 算法简单的递归回文检查器
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21298797/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ Algorithmically Simple Recursive Palindrome Checker
提问by brock
I wrote a string palindrome checker which my instructor says is more complex than it needs to be. I've read similar threads and googled around, but I'm completely stumped as to how to get it to work with fewer steps than this...
我写了一个字符串回文检查器，我的老师说它比它需要的更复杂。我读过类似的帖子并在谷歌上搜索过，但我完全不知道如何用比这更少的步骤让它工作......
void isPal(string str){
int length = str.length();
if(length <= 1) cout << "Palindrome" << endl;//check for zero or one digit numbers
else if(str.at(0) == str.at(length -1)) {
str = str.substr(1, (length - 2));
isPal(str);}
else cout << "Not a palindrome." << endl;{
cin >> str;}
回答by herohuyongtao
Use recursion
使用递归
If you still want to use recursion, do something like:
如果您仍然想使用递归，请执行以下操作：
bool isPal(const string &str, int start, int end)
{
if (start >= end)
return true;
if (str[start] != str[end])
return false;
return isPal(str, ++start, --end);
}
And call isPal(str, 0, str.length()-1)in the main body. The idea is to use two indexes and move them as you don't want to use substr()every time in recursion.
并调用isPal(str, 0, str.length()-1)主体。这个想法是使用两个索引并移动它们，因为您不想substr()每次都在递归中使用。
Without recursion
没有递归
Actually this problem is easy to do without using recursion as follows:
实际上，这个问题很容易在不使用递归的情况下解决，如下所示：
bool isPal(const string &str)
{
int start=0, end=str.length()-1;
while (start < end) {
if (str[start++] != str[end--])
return false;
}
return true;
}
回答by Rashad
Check this:
检查这个：
int is_pal(int start, int end, string &str)
{
if (start >= end)
return 1;
if (str[start] != str[end])
return 0;
return is_pal(++start, --end, str);
}
Call the method from main. Let me know if that helps.. :)
从主调用方法。如果这有帮助，请告诉我.. :)
回答by laune
It should be a function returning true or false, and not print a message. The parameter should be a single string object.
它应该是一个返回 true 或 false 的函数，而不是打印消息。参数应该是单个字符串对象。
bool isPalindrome( const std::string & word ){
std::string::const_iterator fwd = word.begin();
std::string::const_iterator rev = word.end();
if( rev - fwd <= 1 ) return true;
if( *fwd++ != *--rev ) return false;
return isPalindrome( std::string( fwd, rev ) );
}
Later
之后
So a recursivesolution with a single parameterrequires a new string object with each recursion. This has been critizised as being "horrible" - but is it really? An algorithm must be judged in relation to the domain for which it is intended.
因此，具有单个参数的递归解决方案在每次递归时都需要一个新的字符串对象。这被批评为“可怕的”——但真的是这样吗？必须根据其预期的领域来判断算法。
Let's assume that this domain is the words of the English language. There is more than 1.000,000 words in the English language but the number of palindromes is less than 200. So the probability that the recursion has to go all the way to N/2 iterations is almost negligible. Also, the percentage of words with equal first and last letters is very small, and therefore not even a single recursion is required in most cases.
让我们假设这个域是英语的单词。英语有1.000,000多个单词，但回文数不到200。因此递归必须一直进行N/2次迭代的概率几乎可以忽略不计。此外，首尾字母相等的单词的百分比非常小，因此在大多数情况下甚至不需要一次递归。
Another possible domain is random strings composed from the letters 'a' to 'z': more than 96% will not require even a single recursive call. "Horrible"? Hardly.
另一个可能的域是由字母“a”到“z”组成的随机字符串：超过 96% 甚至不需要单个递归调用。“可怕”？几乎不。
If one does want to avoid this "horror", one has three options: avoid recursion, use a second method (to be called from the first) or require more than one argument.
如果确实想避免这种“恐怖”，则有三种选择：避免递归、使用第二种方法（从第一种方法调用）或需要多个参数。
The third variant has been proposed by others, requiring no less than three arguments, asking the user to provide redundant information with a rather messy call, e.g.:
其他人提出了第三种变体，需要不少于三个参数，要求用户通过一个相当混乱的调用提供冗余信息，例如：
string word = "evitative";
bool res = isPal( word, 0, word.length()-1 );
Not really pleasing, is it? - But one can do better than that!
不是很讨人喜欢，是吗？- 但可以做得更好！
bool isPal2( string::const_iterator fwd, string::const_iterator rev ){
return rev - fwd <= 1 || *fwd++ == *--rev && isPal2( fwd, rev );
}
With a moderately complex call:
通过中等复杂的调用：
string word = "reviver";
bool res = isPal2( word.begin(), word.end() );
Now we have avoided the creation of string objects even in those rare cases of palindromes or "palindromoids" at the cost of one additional parameter, at least without redundant information.
现在，即使在那些罕见的回文或“回文”情况下，我们也避免了创建字符串对象，代价是增加一个参数，至少没有冗余信息。
回答by Imtiaz Emu
If you are trying to check whether a string is palindrome or not, you can do it easily as:
如果你想检查一个字符串是否是回文，你可以很容易地做到：
- insert the string into a vectorsuppose v
- reverse the vectorv and insert it to another vector called suppose v1.
- if v == v1, then palindrome, otherwise not.
- 将字符串插入向量假设 v
- 反转向量v 并将其插入另一个称为假设 v1 的向量。
- 如果 v == v1，则回文，否则不是。
i've just suggested a method to check palindrome. nothing else.
我刚刚提出了一种检查回文的方法。没有其他的。
回答by waTeim
Hmm make it not recursive is a try
嗯让它不递归是一个尝试
int i = 0;
int j = str.length() - 1;
bool isPalindrome = true;
while(i < j && isPalindrome)
{
if(str[i++] != str[j--]) isPalindrome = false;
}
回答by Emerson
bool isPalindrome(char str[], int i) {
int x=(strlen(str)-i);
if (i==0) {
return true;
}
if (str[x]!=str[i-1]) {
return false;
}
return isPalindrome(str, i-1);
}
