본문 바로가기

Programming Problems/Strings

String에서 repeating subsequence 존재 여부 찾기

string에서 repeating subsequence를 찾아보자.

예)

abab : sub "abab"가 반복하는 subs이다.

abba : 없음

azcaxc : "acac" 가 반복한다.


풀이 )


bool hasrepeat(string s){

for(int i = 1 ; i <= s.size()-3 ; i++){

if(hasit(s,tmp,i+1)) return true;

}

return false;

}


bool hasit(string s, string tmp, int pos){

// make map

unordered_set<char> tofind;

unordered_set<char> candidates;

for(int i = 0 ; i < pos ; i++){

// set tofind

tofind.insert(s[i]);

}

// go through to check for existance

for(int i = pos ; i < s.size() ; i++){

if(tofind.find(s[i])!=tofind.end()) candidates.insert(s[i]);

if(s[i]==s[pos-1]&& candidates.size()!=0) return true;

}

return false;

}


시간 복잡도 : O(N^2) ,, 첫 함수의 루프에서 N 순회를 하는데 각각에서 그 밑 함수가 O(N)으로 순회하므로 총 O(N^2)가 된다.

공간 복잡도 : O(N) 에 비례