16500 : 문자열 판별

문제

알파벳 소문자로 이루어진 문자열 S와 단어 목록 A가 주어졌을 때, S를 A에 포함된 문자열을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하시오. A에 포함된 단어를 여러 번 사용할 수 있다.

---

입력

첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

출력

A에 포함된 문자열로 S를 만들 수 있으면 1, 없으면 0을 출력한다.

---

예제

softwarecontest
2
software
contest
>> 1

---

풀이

def findStr(idx):
    global result
    
    # 끝까지 탐색했다면? 1
    if idx == len(S):
        result = 1
        return

    # 한번 방문한 문자열이면 재방문 방지를 위해 return
    if dp[idx]: return

	# 방문한 문자열임을 표시
    dp[idx] = 1

    for i in range(len(wordLst)):

        # S 문자열이 비교문자열의 길이보다 작아지면 비교 성립X
        if len(S[idx:]) >= len(wordLst[i]):
			
            for w in range(len(wordLst[i])):
            
            	# 탐색 중 다른 문자열을 발견했을 때! break
                if S[idx+w] != wordLst[i][w]:
                    break
            # 중간에 break 없이 탐색 완료(일치문자열 찾음) 했다면 다음 탐색을 위해 재귀 호출
            else:
                findStr(idx + len(wordLst[i]))
                
    # for문 끝난 후 return (필요없는 연산을 막기 위해) 
    return
    
import sys
S = list(sys.stdin.readline().strip())
N = int(sys.stdin.readline())


dp = [0] * 101
sLen = len(S)
result = 0

wordLst = [sys.stdin.readline().strip() for _ in range(N)]
findStr(0)
print(result)

---

• 만약 if dp[idx]: return 와 dp[idx] = 1가 없다면 아래의 예제에서 result = 1 이 나온다 . 고로 방문처리 필수!

  aaaa
  2
  aa
  a

---

result : 0 예시

S	wordLst[i]	value	recursion / break
softwarecontests	software, conpests	-	index + len(wordLst[i])
S[0:]	S[0+0] == wordLst[0][0]	s	-
S[0:]	S[0+1] == wordLst[0][1]	o	-
S[0:]	S[0+2] == wordLst[0][2]	f	-
S[0:]	S[0+3] == wordLst[0][3]	t	-
S[0:]	S[0+4] == wordLst[0][4]	w	-
S[0:]	S[0+5] == wordLst[0][5]	a	-
S[0:]	S[0+6] == wordLst[0][6]	r	-
S[0:]	S[0+7] == wordLst[0][7]	e	-
-			findStr(0 + 8)
softwarecontests	software, conpests	-
S[8:]	S[8+1] != wordLst[0][1]	c != s	break
softwarecontests	software, conpests	-
S[8:]	S[8+0] == wordLst[1][0]	c	-
S[8:]	S[8+1] == wordLst[1][1]	o	-
S[8:]	S[8+2] == wordLst[1][2]	n	-
S[8:]	S[8+3] != wordLst[1][3]	t != p	break → return
softwarecontests	software, conpests	-
S[0:]	S[0+0] != wordLst[1][0]	s != c	break → return