[leetcode] 문자열 분할

6756 단어 활용단어참조
: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".
영어가 좋지 않으면 제목도 못 읽을 것 같아...문자열과 사전dict를 지정하여 s가 사전의 단어에 따라 한 단어 또는 여러 단어로 나눌 수 있는지 확인합니다.예를 들어 s="leetcode"dict = ["leet", "code"]를true로 되돌려줍니다. "leetcode"는 "leetcode"로 나눌 수 있기 때문입니다.
사고방식: 동적 기획 알고리즘의 사고방식에 따라 상태 F(i): 앞의 i 문자가 분할될 수 있는지를 먼저 찾는다.공식: F (i) = F (j) & substr[j+1, i] (j 초기 상태: F (0) = true 반환 결과: F (n) & & & F & substr[j+1, i] (j 초기 상태: F (0) = true 반환 결과: F (n) 는 문제의 예를 들어 F (1): "&"& & & "l"-> fae ","l "&"& "l"- ":"& "l"- "-": F (0), "L &"& "&"& "&"e ","& "e", "&"e "&"1 & "1"1 & "1 &"1 & "1", "1 & fae"4: 1: 1: 1: 1: 1 "4: 1: 1: 1 j=1,"l"&"eet"-> false j=2,'le'&'et'-> false j=3,'lee'& &'t'-> false.... 이렇게 추측하여 새 그룹은 중간 F(i)의 값을 저장하고 외부 순환 제어 F(i), 내부 순환 제어 [0~i)의 분할 결과를 저장합니다. 구체적인 코드는 다음과 같습니다.
public class ZiFuChuanFenGe {
    public boolean wordBreak(String s, Set<String> dict) {
        if (s.length() <= 0) {
            return false;
        }
        if (dict.isEmpty()) {
            return false;
        }
        boolean[] arr = new boolean[s.length() + 1];
        //   F(0) true
        arr[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] && dict.contains(s.substring(j, i))) {
                    arr[i] = true;
                    break;
                }
            }
        }
        return arr[s.length()];
    }
}

좋은 웹페이지 즐겨찾기