LetCode 면접문제 46.숫자를 문자열로 번역하기 (DFS 경로 총수, 동적 계획)

숫자를 문자열로 번역하다
DFS의 기본적인 방법은 매번 한 자리 또는 두 자리로 전진하고 끝점을 검색하여 누적 1을 더하는 것이다.
class Solution {
public:
    string s;
    int ans = 0;
    int translateNum(int num) {
        s = to_string(num);
        dfs(s,0);
        return ans;
    }
    void dfs(string &s,int idx){
        if(idx==s.size()){
            ans++;
            return;
        }
        dfs(s,idx+1);
        if(idx+1<s.size() && check(s.substr(idx,2))){
            dfs(s,idx+2);
        }
    }
    bool check(string s){
        char a = s[0];
        if(a=='0'){
            return false;
        }
        char b = s[1];
        return int(a-'0')*10 + int(b-'0') <= 25;
    }
};

DP 방법: 100개의 계단과 유사하게 매번 1단계, 후자 2단계를 뛰어넘는데 모두 몇 가지 점프법이 있다.
class Solution {
public:
    int f[15] = {1,1};
    int translateNum(int num) {
        string s = to_string(num);
        for(int i=2;i<=s.size();i++){
            f[i] = f[i-1]+ (check(s.substr(i-2,2))?f[i-2]:0);
        }
        return f[s.size()];
    }
    bool check(string s){
        char a = s[0];
        if(a=='0'){
            return false;
        }
        char b = s[1];
        return int(a-'0')*10 + int(b-'0') <= 25;
    }    
};

좋은 웹페이지 즐겨찾기