단어 연결
설명
고유한 문자열 목록words이 주어지면 목록에 있는 다른 단어를 연결한 단어 수를 반환합니다. 여러 번 연결하고 연결할 때 단어를 재사용할 수 있습니다.
제약 조건:
n ≤ 100,000 여기서 n는 words의 길이입니다.m ≤ 100 여기서 m는 words에서 문자열의 최대 길이입니다.예 1
입력
words = ["news", "paper", "newspaper", "binary", "search", "binarysearch"]
산출
2
설명
"newspaper" is concatenation of "news" and "paper". "binarysearch" is concatenation of "binary" and "search".
예 2
입력
words = ["cc", "c"]
산출
1
설명
"cc" is a concatenation of "c" and "c".
직관
구현
import java.util.*;
class Solution {
private final Set<String> DICTIONARY = new HashSet<>();
public int solve(String[] words) {
Collections.addAll(DICTIONARY, words);
int ans = 0;
for (String word : words) {
if (isConcatenation(word, 0)) {
ans++;
}
}
return ans;
}
private boolean isConcatenation(String wordStr, int wordCount) {
int n = wordStr.length();
if (n == 0) {
return wordCount > 1;
}
for (int i = 1; i <= n; i++) {
String prefix = wordStr.substring(0, i);
if (DICTIONARY.contains(prefix)
&& isConcatenation(wordStr.substring(i), wordCount + 1)) {
return true;
}
}
return false;
}
}
시간 복잡도
import java.util.*;
class Solution {
private final Set<String> DICTIONARY = new HashSet<>();
public int solve(String[] words) {
Collections.addAll(DICTIONARY, words);
int ans = 0;
for (String word : words) {
if (isConcatenation(word, 0)) {
ans++;
}
}
return ans;
}
private boolean isConcatenation(String wordStr, int wordCount) {
int n = wordStr.length();
if (n == 0) {
return wordCount > 1;
}
for (int i = 1; i <= n; i++) {
String prefix = wordStr.substring(0, i);
if (DICTIONARY.contains(prefix)
&& isConcatenation(wordStr.substring(i), wordCount + 1)) {
return true;
}
}
return false;
}
}
Reference
이 문제에 관하여(단어 연결), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/jiangwenqi/word-concatenation-ij8텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
