[Java] 이어 붙인 문자열

1. 문제

문자열 s와 문자열로 이루어진 배열 words 가 주어졌다고 가정한다.

문자열 s가 words 안에 있는 문자열들을 이어붙여 만들 수 있으면 true, 아니면 false를 출력하는 프로그램을 작성하시오.

단, words에 주어진 문자열은 여러 번 재사용할 수 있다.

 

 

2. 입력 설명

• 0 <= s.length <= 1000
• 0 < words.length <= 1000

 

3. 출력 설명

문자열이 구성 가능한지 여부를 논리형으로 출력

 

 

4. 매개변수 형식

s = "zerobase"

words = { "zer", "ro", "ze", "base"}

 

 

 

5. 반환값 형식

true

 

 

 

6. 코드 구현

class Solution {
	boolean result;
    
    public boolean solution(String s, String[] words) {
    	result = false;
        dfs(s,words);
        return result;
    }
    
    void dfs(String s, String[] words) {
        // s 가 빈 문자열인 경우 탈출
    	if(s.equals("")) {
        	result = true;
            return;
        }
        
        // 불필요한 코드 진행을 막기 위해
        // result 가 true 일 경우 반환
        if (result) {
        	return;
        }
        
        // 앞부분이 일치하는 문자열을 찾으면 DFS
        // ex) dfs("zerobase") -> s="zerobase", w="zero" -> dfs("base")
        for(String w : words) {
        	if (s.startsWith(w)) {
            	dfs(s.substring(w.lengh()), words);
            }
        }
    }
}