본문 바로가기

Programming Problems/Strings

string transform 한번에 같은 문자들을 전부 다른 문자로 바꾸는 동작을 할 수 있다.이 동작으로 한 문자열에서 다른 문자열로 바꾸는 것이 가능한지 확인하시오.꼬리문제 : 바꾸는 것이 가능한 문자열이라 할때, 중간에 버퍼를 삽입해야만 바꿀 수 있는 경우가 있다. 이런 경우인지 확인해 보시오.
a,b,c의 조합으로 이루어진 문자열에서 aaa..bb...c.. 형태의 조합의 갯수 우선 DP로 풀이 가능할 듯.int countnumber(string &s, int curr, int it){if(curr==s.size()) return 0;// go throughint ret = 0;for(int i = curr ; i < s.size() ; i++){if(s[i]==it+'a'){ret += countnumber(s,i+1,it);}else if(it!=2&&s[i]==it+'a'+1){ret += ..
ANAGRAM CHECKING 곱셈과 덧셈의 교환법칙에 의해 유일함이 담보된다.아나그람을 체크할때, SUM,PRODUCT를 비교하면 O(M) 으로 만드는 시간만 걸리고 비교는 O(1) 이 걸린다.만약 26개짜리 벡터를 비교하면 O(26) 이어서 조금 더 느리다.시간복잡도는 같다.
스크램블된 문자열을 dict를 이용해 해독해 보자. hello to the world >> elhloothtedrowl이 된다.이때 이걸 해독할 수 있을까? 단어는 전부 딕셔너리에 들어있다.풀이 :각 단어를 카운팅한다. 이제 문자열을 앞에서부터 순회하면서 카운트가 맞는 단어가 있는 경우에 찾아서 그걸 자르고, 빼고( 중복이 가능한가 ?? 여기서는 유일한 조합만 있다고 하자 ) 남은 문자열에서 같은 작업을 재귀해 준다.vector<string> findoriginal(vector&..
n strings를 subsequence로 가지는 가장 lexiographically small한 string 그래프 문제 같은데..?? abcdedrivea > b > c > d > ed > r > i > v > e이런식으로 directed graph가 되고 근데 DAG는 아니라서 topological sort는 안될꺼같은데,이 방법은 아닌거같다. 중복되는 문자들이 계속 나올 수 있는데 구현이 쉽지 않고 큰 의미를 찾기 어렵다.완탐 , DP?최적화?어 이거 그거 될꺼같은데 트라이 만들기 비슷하게 아니면 앞..
string 앞에다가 최소한의 문자를 더해서 palindrome 만들기. 최소 갯수는? 일치하는 subfix와 postfix의 최대 길이를 물어보는건가?bcacbcaabbc나이브하게는 하나씩 더하면서 팰린드롬인지 확인.. ( 무생각 )..아아.. 왼쪽에서만 추가하니까.. 결국에는 오른쪽에 이상한게 있으면 전부 보충해줘야 한다.즉, 뒤집은 문자열을 하나 만들고(이게 상한이다) 겹치는 만큼 줄인다.abccd >> dccba abccdbazcbbczab >> 1개 겹치니까(뒤집은거의 앞에서부터) 4개 추가해서 bczab..
두개의 스트링이 주어졌을 떄, 불연속적인 섭스트링의 갯수를 구해라 ex) "cat", "catapult">> "CATapult", "CatApulT", "CAtapulT"답 : 3솔루션 : 우선 바로 떠오르는 방법은 없으니 나이브에서 시작하자. DP로 비벼지는게 보인다 O(MN)으로.int findall(string & s, string & t, int scurr, int tcurr){if(tcurr==t.size()) return 1;// go through starting from sc..
k개의 종류로 이루어진 최대 길이 스트링 찾기 Q ex ) aaaabbbb, k=2 >> aaaabbbbasdfrttt, k=3 >> frttt나이브 솔루션 : 긴 섭스트링부터 안에 있는 원소의 수가 맞는지 본다. O(N^3) 알고리즘.해시 테이블을 이용한 트래킹.헤드 테일을 곁들여서.헤드를 늘려 가면서 맵에 원소의 수와 갯수를 체크한다.갯수가 K 일때 길이를 확인한다.K 보다 갯수가 많아지만 tail을 앞으로 보내면서 하나씩 뺀다.갯수가 K일때 길이를 확인한다.head를 K보..