c++ 为什么有效回文的代码对单边情况不起作用?[已结束]

nle07wnf  于 2022-12-05  发布在  其他
关注(0)|答案(3)|浏览(116)

**已关闭。**此问题需要debugging details。当前不接受答案。

编辑问题以包含desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem。这将有助于其他人回答问题。
昨天关门了。
Improve this question
下面是我的代码从leetcode。我认为我已经写了适当的逻辑代码,但它不工作,只为边缘情况-“赛车”。它返回真,但它应该是假的。为什么它是?问题链接-https://leetcode.com/problems/valid-palindrome
我知道我可以在解决方案部分找到更多方法的答案,但我想知道我的代码中缺少什么。

class Solution {
public:
    bool isPalindrome(string s) {
        int st =0, e=s.size()-1;
        vector<char> ans1;
        vector<char> ans2;
        while(st<=e){
            
            if((s[st] >= 'a' && s[st] <= 'z') || (s[st] >= 'A' && s[st] <= 'Z') || (s[st] >= '0' && s[st] <= '9')){
                ans1.push_back(islower(s[st]));
                
            }
            if((s[st] >= 'a' && s[st] <= 'z') || (s[st] >= 'A' && s[st] <= 'Z') || (s[st] >= '0' && s[st] <= '9')){
                ans2.push_back(islower(s[e]));
            }

            st++;
            e--;
        }
        if(ans1 == ans2){return 1;}
        return 0;
    }
};
kdfy810k

kdfy810k1#

代码存在一些问题。
首先,条件(s[st]〉= 'a' && s[st]〈= 'z')||(s[st]〉= 'A' && s[st]〈= 'Z')||(s[st]〉= '0' && s[st]〈= '9')只检查字符是字母还是数字。这意味着其他字符(如空格和标点符号)将被忽略。
第二,代码只将字母或数字字符推送到ans 1和ans 2向量上。这意味着任何空格或标点符号都将被忽略,这可能导致不正确的结果。例如,字符串“A man,a plan,a canal,Panama!”是回文,但您的代码不会将其识别为回文,因为它忽略了空格和标点符号。
第三,在将字符添加到ans 1和ans 2向量之前,代码使用islower函数将字符转换为小写。但是,islower并不实际修改字符--如果字符为小写,它只返回true,否则返回false。要实际将字符转换为小写,应该使用tolower函数。
最后,代码比较ans 1和ans 2向量,以确定原始字符串是否为回文。但是,这不是一种可靠的检查字符串是否为回文的方法,因为向量中字符的顺序可能与原始字符串中字符的顺序不匹配。例如,字符串“Able was I ere I saw Elba”就是回文。但是代码将无法识别它,因为ans 1和ans 2向量中的字符顺序相反。
若要修正这些问题,您可以修改程式码,如下所示:
使用正则表达式只匹配输入字符串中的字母和数字。这将允许您忽略任何其他字符,如空格和标点符号。使用tolower函数将匹配的字符转换为小写,以便您的代码可以处理混合了大小写字母的回文。使用单个向量存储匹配和转换的字符,并将此向量中的字符与向量的反转版本进行比较,以确定原始字符串是否为回文。这将确保保留字符的顺序。以下是修改后的代码的示例:

class Solution {
public:
    bool isPalindrome(string s) {
        // Use a regular expression to match only letters and numbers in the input string
        regex r("[a-zA-Z0-9]");

        // Create a vector to store the matched and converted characters
        vector<char> chars;

        // Iterate over the characters in the input string
        for (char c : s) {
            // If the current character is a letter or number, convert it to lowercase and add it to the vector
            if (regex_match(string(1, c), r)) {
                chars.push_back(tolower(c));
            }
        }

        // Check if the vector is equal to its reversed version
        return chars == vector<char>(chars.rbegin(), chars.rend());
    }
1mrurvl1

1mrurvl12#

class Solution {
public:
    bool isPalindrome(string s) {
        // Create a vector to store the converted characters
        vector<char> chars;

        // Iterate over the characters in the input string
        for (char c : s) {
            // If the current character is a letter or number, convert it to lowercase and add it to the vector
            if (isalnum(c)) {
                chars.push_back(tolower(c));
            }
        }

        // Check if the vector is equal to its reversed version
        return chars == vector<char>(chars.rbegin(), chars.rend());
    }
}
3pvhb19x

3pvhb19x3#

在第二个循环中,您使用了错误的索引s[st],而不是s[e]!因此,如果s[st]不是字符或数字,则忽略s[e]
顺便说一句,您的字符测试是不可移植的:虽然C语言保证数字按升序排列,但字母不一定如此--考虑一下(-?)著名的EBCDIC编码!
所以对于字母的测试,你应该使用isalpha函数来代替,对于数字,我推荐使用isdigit。对于 * 任一个 *,也有isalnum,这是你所需要的。
但是要注意,所有这些都接受int,并且char * 可能 * 有符号。扩展范围(128 - 255)中的字符将导致负值,因此您应该将输入转换为unsigned char
然后你接受字符串 by value,这样你就得到了一个副本,然后从中获益,把字符串转换成较低的 * 代替 *,忽略运行中的标点符号:

auto pos = s.begin();
for(unsigned char c : s) // explicitly specifying the type performs the necessary cast!
{
    if(isalnum(c))
    {
        // this moves the alnums, already lowered in case, towards
        // front, overwriting the unwanted punctuation marks:
        *pos++ = tolower(c);
    }
}
// cut off the remaining ballast, i.e. the places of the moved characters (if any):
s.erase(pos, s.end());

好的,现在s包含了一个全小写字符的字符串(注意,有些语言对同一个字符有不止一种表示,比如希腊语的'Σ'(Sigma),小写的'σ'在单词的开头或中间,'ς'在单词的结尾),这种方法无法覆盖这些字符。
现在,你可以复制字符串,反转它(std::reverse),然后比较反转后的副本和原始字符串是否相等--或者,你可以直接比较对应的字符来节省这部分精力:

for(auto b = s.begin(), e = s.end() - 1; b < e; ++b, --e)
{
    if(*b != *e)
    {
        return false;
    }
}
return true;

请注意,这在空字符串上会失败,您可能会在开始时(甚至在转换为lower之前)捕捉到这种特殊情况:

if(s.empty())
{
    return true; // depending on definition, usually empty string does
                 // count as palindrome
}

实际上,您甚至可以在一次运行中完成所有这些操作;但是,这会导致非常高级的代码,这可能超出了本问题的范围;如果您仍对以下内容感兴趣:请参阅godbolt。请特别注意,通过const引用接受字符串,可以完全避免复制字符串。

相关问题