[해커랭크] Two Strings (C++)

문제 링크: www.hackerrank.com/challenges/two-strings/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

Two Strings | HackerRank

1. 주의할 점

- 문제를 잘 읽자

- KMP 알고리즘을 사용하지 않아도 된다

 

2. 구현

- 3가지 방법으로 접근했지만 성공한것은 1개 뿐

 

(1) Set, 시간복잡도: O(N^2*M^2) -> TLE(4/8 성공)

- s1의 각 substring을 Set s에 대입한다

- s2의 각 substring을 Set s에서 find해서 있으면 "YES" 없으면 "NO"를 리턴한다

 

(2) KMP 알고리즘, 시간복잡도(불확실하지만): O((N+M)*M) -> TLE(5/8 성공)

- s1의 각 substring을 pattern으로 지정하고 s2를 origin으로 지정하여 KMP 알고리즘을 수행한다. 단, 패턴이 모두 일치할때까지가 아닌, 1개라도 일치하면 true반환

vector<int> getPi(string ptn){
    int len = ptn.size();
    vector<int> pi(len,0);
    int j=0;
    for(int i=1;i<len;i++){
        while(j>0 && ptn[i]!=ptn[j]){
            j = pi[j-1];
        }
        if(ptn[i]==ptn[j])
            pi[i]=++j;
    }
    return pi;
}

bool KMP(string org, string ptn){
    vector<int> pi = getPi(ptn);
    int j=0;
    for(int i=0;i<org.size();i++){
        while(j>0 && org[i]!=ptn[j]){
            j = pi[j-1];
        }
        if(org[i]==ptn[j]){
            return true;           
        }
    }
    return false;
}

string twoStrings(string s1, string s2) {
    for(int i=0;i<s2.size();i++){
        string ss = s2.substr(i);
        if(KMP(s1,ss)) return "YES";
    }
    return "NO";
}

 

(3) Set, 시간복잡도: O(N+M*lg(N)) -> 통과

- 1글자라도 같으면 "YES"반환에서 모든 로직 축소

- s2의 모든 글자를 Set s에 추가

- s1의 모든 글자를 s에서 검색하여 있으면 "YES", 없으면 "NO"반환

string twoStrings(string s1, string s2) {
    set<int> s;
    for(int i=0;i<s2.size();i++){
        s.insert(s2[i]);
    }
    for(int i=0;i<s1.size();i++)
        if(s.find(s1[i])!=s.end())
            return "YES";
    return "NO";
}