LetCode 매일 한 문제:분사1

979 단어
문제 설명
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s ="leetcode", dict =["leet", "code"]. Return true because "leetcode"can be segmented as"leet code".
문제 분석
전형적인 동적 기획은 dp[i]를 설정하여 s의 0에서 i위가 나눌 수 있는지 여부를 나타낸다. 그러면 상태 이동 방정식은 다음과 같다. dp[i]=dp[j]가 나눌 수 있는지+s[j,i]가 나눌 수 있는지, 그 중에서 j의 수치 범위는 [0,i] 사이이기 때문에 우리는 s[j,i]가 dict에 포함되었는지 판단하면 된다.
코드 구현
public boolean wordBreak(String s, Set dict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];//dp[i]  s 0 i  
        dp[0] = true;
        for (int i = 1; i <= len; i++)
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        return dp[len];
    }

좋은 웹페이지 즐겨찾기