본문 바로가기

Programming Problems/Strings

스크램블된 문자열을 dict를 이용해 해독해 보자.

hello to the world >> elhloothtedrowl이 된다.

이때 이걸 해독할 수 있을까? 단어는 전부 딕셔너리에 들어있다.


풀이 :


각 단어를 카운팅한다. 이제 문자열을 앞에서부터 순회하면서 카운트가 맞는 단어가 있는 경우에 찾아서 그걸 자르고, 빼고( 중복이 가능한가 ?? 여기서는 유일한 조합만 있다고 하자 ) 남은 문자열에서 같은 작업을 재귀해 준다.


vector<string> findoriginal(vector<string> & data, string & s){

// 벡터 키는 안되지만 된다고 가정. 비트 수준으로 숫자 조합을 모은 다음에 해시로 뭉개버리면 된다.

unordered_map<vector<int>,int> dict;

for(int i = 0 ; i < data.size() ; i++){

vector<int> counter(26,0);

for(int j = 0 ; j < data[i].size() ; j++){

counter[data[i][j]-'a']++;

}

dict.insert(pair<vector<int>,int>(counter,i));

}

return findoriginal(dict,s,curr);

}


vector<string> findoriginal(unordered_map<vector<int>,int> & dict, string & s, int curr){

if(curr==s.size()) return vector<string>():

// count map all words in dict


// 앞에서부터 순회하면서 카운트가 맞는 단어가 있으면 제시한다.

vector<string> ret = "";

vector<int> counter(26,0);

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

counter[s[i]-'a']++;

auto it = dict.find(counter);

if(it!=dict.end()){

vector<string> tmp = findoriginal(dict,s,i+1);

ret.insert(ret.end(),tmp.begin(),tmp.end()):

}

}

return ret;

}


재밌는건, dict에서 중복 사용이 가능하면 DP 가 가능해서 O(N^2) 알고리즘으로 캐핑이 가능하지만 만약 중복 사용이 불가능하면.. 디피가 안된다 .. ㅠㅠ 완전탐색이 되어버린다... 아닌가??