Solution For Longest String Chain

The Longest String Chain problem on LeetCode is a dynamic programming problem that requires finding the longest chain of words in a given list such that each word in the chain is formed by deleting one letter from the previous word.

To solve this problem, we can first sort the words based on their lengths. We can then build a dictionary of words where the key is the word itself and the value is the length of the longest chain that can be built starting from this word.

For each word in the list, we can delete one letter at a time and check if the resulting word is in our dictionary. If the resulting word is in the dictionary, we can update its chain length value by taking the maximum value of the current chain length and adding one to it.

We can repeat this process for all the words in the list and return the maximum value in the dictionary.

The time complexity of this solution is O(n*w^2), where n is the number of words in the list and w is the maximum length of a word in the list. This is because we iterate through each word and for each word, we delete each of its letters and check if the resulting word is in our dictionary.

Here is the Python code for the solution:

“`
def longestStrChain(words):
words.sort(key=len)
word_dict = {}
max_chain_len = 1

for word in words:
    word_dict[word] = 1
    for i in range(len(word)):
        new_word = word[:i] + word[i+1:]
        if new_word in word_dict:
            word_dict[word] = max(word_dict[word], word_dict[new_word]+1)
    max_chain_len = max(max_chain_len, word_dict[word])

return max_chain_len

“`

We start by sorting the words in the list based on their lengths. We then initialize an empty dictionary to store the chain length values for each word and set the maximum chain length to 1.

For each word in the list, we set its chain length value in the word_dict to 1. We then iterate through each letter in the word and delete it to create a new_word. If the new_word is in our dictionary, we update the chain length value for the current word by taking the maximum value of its current chain length and adding one to the chain length of the new_word.

We update the max_chain_len variable with the maximum chain length value seen so far and return it at the end of the loop.

Step by Step Implementation For Longest String Chain

class Solution {
    public int longestStrChain(String[] words) {
        
        // sort the array of words by length
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        
        // create a map to store the length of the longest chain 
        // for each word
        Map map = new HashMap<>();
        
        // initialize the longest chain length to 1 for each word
        for (String word : words) {
            map.put(word, 1);
        }
        
        // iterate through the array of words
        for (String word : words) {
            
            // for each character in the word
            for (int i = 0; i < word.length(); i++) {
                
                // create a new string by removing the character at index i
                String newWord = word.substring(0, i) + word.substring(i+1);
                
                // if the new string is in the map and its length is 
                // one less than the current word
                if (map.containsKey(newWord) && map.get(newWord) == map.get(word) - 1) {
                    
                    // update the longest chain length for the current word
                    map.put(word, map.get(newWord) + 1);
                }
            }
        }
        
        // return the longest chain length
        return Collections.max(map.values());
    }
}

def longestStrChain(words):
    
    # sort the list of words by length
    words.sort(key=len)
    
    # initialize a dictionary to store the length of the longest chain 
    # for each word
    d = {}
    
    # for each word in the list of words
    for word in words:
        
        # if the word is not in the dictionary, 
        # set the length of the longest chain to 1
        if word not in d:
            d[word] = 1
            
        # for each letter in the word
        for i in range(len(word)):
            
            # remove the ith letter from the word to create a new word
            new_word = word[:i] + word[i+1:]
            
            # if the new word is in the dictionary
            if new_word in d:
                
                # update the length of the longest chain for the word
                # by incrementing the length of the longest chain for the new word
                d[word] = max(d[word], d[new_word] + 1)
                
    # return the length of the longest chain for the last word in the list
    return d[words[-1]]

var longestStrChain = function(words) {
    
    // sort the words by length
    words.sort((a,b) => a.length - b.length);
    
    // create a map to store the words and their longest chains
    const map = new Map();
    
    // iterate through the words
    for (const word of words) {
        
        // set the longest chain for the current word to 1
        let longest = 1;
        
        // iterate through all the letters in the current word
        for (let i = 0; i < word.length; i++) {
            
            // create a variable for the current word minus the letter at the current index
            const current = word.slice(0,i) + word.slice(i+1);
            
            // if the current word minus the letter at the current index is in the map
            if (map.has(current)) {
                
                // update the longest chain for the current word if it's longer than the current longest chain
                longest = Math.max(longest, map.get(current) + 1);
            }
        }
        
        // update the map with the current word and its longest chain
        map.set(word, longest);
    }
    
    // return the longest chain in the map
    return Math.max(...map.values());
};

The problem is to find the longest chain of words, where each word in the chain is a successor of the previous word. A word X is a successor of another word Y if X can be formed by Y by adding a letter, removing a letter, or changing a letter.

One solution is to use a dynamic programming approach, where we store the length of the longest chain that includes each word in a map. Then, we iterate through all of the words in the given list, and for each word, we consider all of the other words to see if they can be added to the current chain. If so, we update the map accordingly.

#include 
#include 
#include 
#include 

public int LongestStrChain(string[] words) { // Create a dictionary to store all of the words and their // length. This will be used to quickly lookup the length // of a given word. var wordLengths = new Dictionary(); foreach (var word in words) { wordLengths[word] = word.Length; } // Sort the words by length, in ascending order. This will // ensure that when we iterate through the words, we will // always be considering a "longer" word before a "shorter" // word. Array.Sort(words, (a, b) => wordLengths[a] - wordLengths[b]); // Create a variable to track the length of the longest // string chain. var longestChain = 0; // Iterate through each word in the sorted array. for (var i = 0; i < words.Length; i++) { // Create a variable to track the length of the current // string chain. var currentChain = 0; // Iterate through each word, starting at the next word // in the array. for (var j = i + 1; j < words.Length; j++) { // If the current word is not one letter longer than // the previous word, we can't add it to the chain, so // we can break out of this loop. if (wordLengths[words[j]] != wordLengths[words[i]] + 1) { break; } // Check to see if the current word can be added to the // chain. if (CanAddToChain(words[i], words[j])) { // The current word can be added to the chain, so // increment the length of the current chain. currentChain++; // If the current chain is longer than the longest // chain, update the longest chain variable. if (currentChain > longestChain) { longestChain = currentChain; } } } } return longestChain; } private bool CanAddToChain(string word1, string word2) { // This method returns true if the second word can be added // to the chain that starts with the first word. // // We know that the second word is exactly one letter longer // than the first word, so we can iterate through each // character in the first word, and compare it to the // corresponding character in the second word. If we find a // difference, we can check to see if the character that is // in the second word is present in the first word. // // For example, if we are considering the words "a" and "ab", // we would compare the first letter of each word. We would // find that they are different, and then check to see if // "b" is present in "a". It is, so we return true. // // If, on the other hand, we were considering the words "abc" // and "abd", we would compare the first two letters of each // word, and find that they are the same. We would move on to // the next letter and find that they are different. We would // then check to see if "d" is present in "abc", and it is not, // so we return false. for (var i = 0; i < word1.Length; i++) { // If the characters at the current index are different, // we need to check to see if the character from the // second word is present in the first word. if (word1[i] != word2[i]) { // The characters are different, so check to see if the // character from the second word is present in the // first word. return word1.Contains(word2[i]); } } // If we get to this point, it means that all of the // characters in the two words are the same, so we return // true. return true; }