Lesson 5 : Nesting (Nesting)

Lesson 5 : Nesting
https://codility.com/programmers/lessons/5

メモリ使用量を O(1)で解けとの課題。

方針としては、'('と')'の数がマッチしていればよい。ただし、途中で'）'の数が増えていると、間違った文字列が与えられているということになることに注意。また、空文字列も許容される。

これで１００％のスコアがもらえます。

int solution(char *S) 
{
    int lnum = 0;
    int rnum = 0;
    
    char *p = S;
    
    //the string can be empty. no need to scan.
    if (*p == NULL){
        return 1;
    }
    
    while(*p != NULL){
        if (*p == '('){
            lnum++;
        }
        else {
            //the number of ')' can never exceed the number of '('
            rnum++;
            if (rnum > lnum){
                return 0;
            }
        }
        p++;
    }
    
    return lnum == rnum;
}