[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()];
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
제이티의 사용에 대한 상세한 설명Continuation 메커니즘을 이용하여 대량의 사용자 요청과 비교적 긴 연결을 처리한다.또한 Jetty는 매우 좋은 인터페이스를 설계했기 때문에 Jetty의 어떤 실현이 사용자의 수요를 만족시키지 못할 때 사용자...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.