청정알고리즘

문제

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.'.' Matches any single character. '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

풀이

동적계획법(Dynamic Programming)을 이용한다.

$sl, pl$을 각각 $s, p$의 길이라고 하자. 그 후 $f$를 다음과 같이 정의한다.

$f(si, pi) =$ ( $s[si:]$와 $p[pi:]$가 matching 되는지의 여부)

그러면 다음과 같은 경우로 나눌수 있다.

case 1) $pi==pl$인 경우

이 경우에는 다음 패턴이 존재하지 않으므로 현재의 s와 완벽히 매칭이 되어야 한다.

case 2) $p[pi+1]$이 '*'이 아닌 경우

이 경우는 $s[si]$와 $p[pi]$가 매칭되면서 $f(si+1, pi+1)$이 참이면 $f(si,pi)$도 참이 된다.

나머지 경우에는 뒤쪽이 안맞거나 현재가 안 맞으므로 거짓이 된다.

case 3) $p[pi+1]$이 '*'인 경우

이 경우는 $s[i]$가 없을 수도, 여러개 나올 수도 있다.

s[i]가 없이 매칭되는 경우는 $f(si, pi+2)$가 된다. ('?*'를 제거)

s[i]가 있으면서 매칭되는 경우는 $s[si]$와 $p[pi]$가 매칭되면서 $f(si+1, pi)$가 참이어야 $f(si,pi)$가 참이 된다.

위 세가지 경우가 존재하는 모든 경우며 이를 이용해서 동적계획법을 구현하면 된다.

Time Complexity : $O(|S||P|)$

코드

class Solution {
private:
    vector< vector<int> > dp;
    int sl, pl;
    string S, P;
public:
    bool isMatch(string s, string p) {
        S=s, P=p;
        sl=s.length(), pl=p.length();
        
        dp.resize(sl+1);
        for(int i=0;i<=sl;i++)dp[i].resize(pl+1,-1);
        return f(0,0);
    }
    
    bool f(int si, int pi)
    {
        if(si>sl)return false;
        int& ret=dp[si][pi];
        if(dp[si][pi]!=-1) return ret;

        if(pi==pl) return ret=(si==sl)?1:0;
        bool match = (si<sl && (P[pi] == S[si] || P[pi]=='.'));
        if(pi+1<pl && P[pi+1]=='*')
            return ret = f(si, pi+2) || (match && f(si+1,pi));
        return ret = f(si+1, pi+1) && match;
    }
};

문제

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

풀이

음수인 경우는 무조건 false를 return한다.

양수인 경우에는 Reverse Integer를 구해서 같은지 체크한다.

Time Complexity : $O(logn)$

코드

class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0) return false;
        long long num=0, t=x;
        while(t)
        {
            num = num*10+t%10;
            t/=10;
        }
        return x==num;
    }
};

문제

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

풀이

우선 글의 앞에 공백이 있을 수도 있으니, 앞에 있는 공백을 전부 제거한다.

그 후 가장 첫 글자가 부호인 경우에 $sgn$변수에 부호를 저장해준다.

그리고 정답을 저장하는 변수인 $ans$에 $ans=ans*10 + str[i]-\text{'0'}$를 계속 더해주면 된다.

Reverse Integer 문제와 마찬가지로 boundary case처리를 해주면 끝난다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int myAtoi(string str) {
        int st, ans=0, sgn=1;
        for(st=0;str[st]==' '&&st<str.length();st++);
        
        if(str[st]=='-')
        {
            sgn=-1;
            st++;
        }
        else if(str[st]=='+') st++;
        
        for(int i=st;i<str.length();i++)
        {
            if(str[i]<'0' || str[i]>'9') break;
            int num = str[i]-'0';
            if(ans>INT_MAX/10 || (ans==INT_MAX/10 && num>7)) return INT_MAX;
            if(ans<INT_MIN/10 || (ans==INT_MIN/10 && num>8)) return INT_MIN;
            ans = ans * 10 + num*sgn;
        }
        return ans;
    }
};