1048. Longest String Chain

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

El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.

LeetCode Static

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

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

Ejemplo:

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

Output: 4

C# solución

coincidente/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++ solución

borrador automático, revisar antes de enviar

#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 solución

coincidente/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 solución

coincidente/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 solución

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

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes

Todavía no hay vacantes activas.