1048. Longest String Chain

LeetCode easy original: C# #array #csharp #dynamic-programming #easy #hash-table #leetcode #math #sort #string #tree

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

Вам дан mảng слов, каждое из которых состоит из строчных английских букв. СловоА является предшественником словаВ тогда и только тогда, когда мы можем вставить ровно одну букву в любое место словаА, не меняя порядка остальных символов, чтобы оно стало равно словуВ.

НаVí dụ, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. return длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов.

Ví dụ:

Input: words = ["a","b","ba","bca","bda","bdca"]

Output: 4

C# lời giải

đã khớp/gốc

using System;
using System.Collections.Generic;
public class Solution {
    public int LongestStrChain(string[] words) {
        Array.Sort(words, (a, b) => a.Length - b.Length);
        var dp = new Dictionary<string, int>();
        int longestChain = 1;
        
        foreach (var word in words) {
            dp[word] = 1;
            for (int i = 0; i < word.Length; i++) {
                string predecessor = word.Substring(0, i) + word.Substring(i + 1);
                if (dp.ContainsKey(predecessor)) {
                    dp[word] = Math.Max(dp[word], dp[predecessor] + 1);
                }
            }
            longestChain = Math.Max(longestChain, dp[word]);
        }
        
        return longestChain;
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LongestStrChain(vector<string> words) {
        Array.Sort(words, (a, b) => a.size() - b.size());
        var dp = new unordered_map<string, int>();
        int longestChain = 1;
        
        foreach (var word in words) {
            dp[word] = 1;
            for (int i = 0; i < word.size(); i++) {
                string predecessor = word.Substring(0, i) + word.Substring(i + 1);
                if (dp.count(predecessor)) {
                    dp[word] = max(dp[word], dp[predecessor] + 1);
                }
            }
            longestChain = max(longestChain, dp[word]);
        }
        
        return longestChain;
    }
}

Java lời giải

đã khớp/gốc

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Map<String, Integer> dp = new HashMap<>();
        int longestChain = 1;
        
        for (String word : words) {
            dp.put(word, 1);
            for (int i = 0; i < word.length(); i++) {
                StringBuilder sb = new StringBuilder(word);
                String predecessor = sb.deleteCharAt(i).toString();
                if (dp.containsKey(predecessor)) {
                    dp.put(word, Math.max(dp.get(word), dp.get(predecessor) + 1));
                }
            }
            longestChain = Math.max(longestChain, dp.get(word));
        }
        
        return longestChain;
    }
}

JavaScript lời giải

đã khớp/gốc

function longestStrChain(words) {
    words.sort((a, b) => a.length - b.length);
    let dp = new Map();
    let longestChain = 1;
    
    for (let word of words) {
        dp.set(word, 1);
        for (let i = 0; i < word.length; i++) {
            let predecessor = word.slice(0, i) + word.slice(i + 1);
            if (dp.has(predecessor)) {
                dp.set(word, Math.max(dp.get(word), dp.get(predecessor) + 1));
            }
        }
        longestChain = Math.max(longestChain, dp.get(word));
    }
    
    return longestChain;
}

Python lời giải

đã khớp/gốc

def longestStrChain(words):
    words.sort(key=len)
    dp = {}
    longest_chain = 1
    
    for word in words:
        dp[word] = 1
        for i in range(len(word)):
            predecessor = word[:i] + word[i+1:]
            if predecessor in dp:
                dp[word] = max(dp[word], dp[predecessor] + 1)
        longest_chain = max(longest_chain, dp[word])
    
    return longest_chain

Algorithm

1⃣Отсортируй список слов по длине.

2⃣Используй dynamic programming для вычисления длины самой длинной цепочки для каждого слова.

3⃣Верни максимальную длину среди всех цепочек.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.