CODEWITHSUNDEEP
c++stringc++11
user15230795
user15230795

Reputation:

C++ runtime error: addition of unsigned offset?

I wrote the following to check if text is palindrome, I run it on leetcode and I am getting errors:

class Solution {
public:
    bool isPalindrome(string s) {
        int l=0,r=s.length()-1;
        while(l<r)
        {
            while (!isalpha(s[r]))
            {
                --r;
            }
            while (!isalpha(s[l]))
            {
                ++l;
            }
            if (tolower(s[r])!=tolower(s[l]))
                return false;
            --r;
            ++l;
        }
        return true;
    }
};

Line 1061: Char 9: runtime error: addition of unsigned offset to 0x7ffc7cc10880 overflowed to 0x7ffc7cc1087f (basic_string.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/basic_string.h:1070:9

what's the problem with my code?

Upvotes: 1

Views: 8684

Answers (4)

Johnny
Johnny

Reputation: 125

As others have said, you are running out of bonds. Here is a simplified solution that will not run out of bonds and also is free of if-then-else spaghetti code:

bool IsPalindrome(const char *s)
{
    int forward, totLen, halfLen, backward;

    totLen = (int)strlen(s);    // Total length
    halfLen = totLen / 2;       // Half the length, if totLen is odd, will ignore the character in the middle

    for (forward = 0; forward < halfLen; forward++) // Index from front of string
    {
        backward = totLen - (forward + 1);          // Corresponding index from back of string
        if (s[forward] != s[backward])
            return false;                           // Not a palindrome
    }
    return true;    // Got one!
}

Upvotes: -1

Prajwal Singh
Prajwal Singh

Reputation: 337

A similar modified approach, where you continue the loop whenever you encounter any non-alphanumeric char solves the problem. Here:

bool isPalindrome(string s) {    
    int start=0,end=s.length()-1;
    
    while(start<=end){
        if(!isalpha(s[start])  && !isdigit(s[start])){
            start++;
            continue;
        }
        
        if(!isalpha(s[end]) && !isdigit(s[end])){
            end--;
            continue;
        }
        
        if(tolower(s[start])!=tolower(s[end])){
            return false;
        }
        
        start++;
        end--;
    }
    
    return true;

}

Upvotes: 0

Stefano Buora
Stefano Buora

Reputation: 1062

I think you were very close to the solution. The pitfall here are that:

  • you are modifying the loop control variable more than once in the loop
  • (as consequence) you are using the loop control variable after changing their values without further checks.

The easy way to fix this kind of issue is to do one single action for every iteration. you can achieve this just using "else".

class Solution {
public:
    bool isPalindrome(string s) {
        int l=0,r=s.length()-1;
        while(l<r)
        {
            if(!isalpha(s[r]))
            {
                --r;
            }
            else if(!isalpha(s[l]))
            {
                ++l;
            }
            else if (tolower(s[r])!=tolower(s[l]))
            {
                return false;
            }
            else
            {
                --r;
                ++l;
            }
        }
        return true;
    }
};

Upvotes: 0

Thomas Sablik
Thomas Sablik

Reputation: 16453

You're going out of bounds here:

while (!isalpha(s[r]))

and here

while (!isalpha(s[l]))

r can became negative and l can become >= s.length().

You should add some checks like

while (l < r && !isalpha(s[r]))

and

while (l < r && !isalpha(s[l]))

The same problem in this line

if (tolower(s[r])!=tolower(s[l]))

This should be

if (l < r && tolower(s[r])!=tolower(s[l]))

Different approach (C++20)

A different approach is to erase all non-alpha characters from s with

std::erase_if(s, [](char c) { return !isalpha(c); });

and remove the inner while loops.

Upvotes: 3

Related Questions