1048. Longest String Chain

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

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

LeetCode Static

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

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

Beispiel:

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

Output: 4

C# Lösung

zugeordnet/original

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ösung

Auto-Entwurf, vor dem Einreichen prüfen

#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ösung

zugeordnet/original

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ösung

zugeordnet/original

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ösung

zugeordnet/original

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⃣Верни максимальную длину среди всех цепочек.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.