LeetCode 1048. Longest String Chain?
19339 단어 LeetCodeDynamicProgrammingJava
so we are given a list of words, Return the longest possible length of a word chain with words chosen from the given list of words.
sounds a lot like LC1024 which I can’t really think of using DP in this problem. but since now i do, let’s try to solve it in brute force and then DP. brute force: find each and every chain and get the longest chain. how to find each and every valid chain? we do checking, but the checking will takes us so much time complexity to do that so i don;t think that will do it.
so now let’s try dp: let’s assume dp[i] is the longest possible length of chain if we only have i words. if (words[i] and words[j] only difference in one letter, and words[i] is the longer one, so at least we should presort the given words by length of word) dp[i] = dp[j] + 1…in this case we return the last element of dp
or we can assume dp[i] is the longest chain that end with words[i], in this case we return the maximum of dp but the code is not right, although i believe it’s right idea.
class Solution {
public int longestStrChain(String[] words) {
if (words == null || words.length <= 1) return 0;
int m = words.length;
int[] dp = new int[m + 1];
Arrays.sort(words, (a, b) -> a.length() - b.length());
Arrays.fill(dp, 1);
dp[0] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 0; j < i; j++) {
if (diff(words, i - 1, j)) {
//if word
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
//System.out.println(dp[i]);
}
System.out.println(dp[3]);
System.out.println(dp[4]);
System.out.println(diff(words, 4, 3));
int max = Integer.MIN_VALUE;
for (int i = 0; i <= m; i++) {
max = Math.max(max, dp[i]);
}
return max;
}
private boolean diff(String[] words, int i, int j) {
//i is larger and j is smaller
//so let's check add one letter in words[j] we can get words[i], remember: the original order shouldn't change too
int m = words[i].length();
int n = words[j].length();
if (m - n != 1) {
return false;
}
//now we can sure that the lenngth between those two are one
int s = 0;//pointer on j, because j is the shorter one
int l = 0;
int counter = 0;
while (s < n && l < m) {
if (words[j].charAt(s) != words[i].charAt(l)) {
if (counter > 1) {
return false;
}
counter++;
l++;
} else {
s++;
l++;
}
}
return true;
}
}
더 좋 은 시간 복잡 도 답 이 있어 요.
class Solution {
public int longestStrChain(String[] words) {
Map<String, Integer> dp = new HashMap<>();
Arrays.sort(words, (a, b)->a.length() - b.length());
int res = 0;
for (String word : words) {
//for each word we checks every possiblity of its previous in the chain
int best = 0;
for (int i = 0; i < word.length(); ++i) {
String prev = word.substring(0, i) + word.substring(i + 1);
best = Math.max(best, dp.getOrDefault(prev, 0) + 1);
}
dp.put(word, best); //update
res = Math.max(res, best); //get the best from the best
}
return res;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.