Leetcode Longest word in dictionary through deleting problem solution

In this Leetcode Longest word in a dictionary through deleting problem solution, we have given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Leetcode Longest word in dictionary through deleting problem solution in Python.

def findLongestWord(self, S, D):
    D.sort(key = lambda x: (-len(x), x))
    for word in D:
        i = 0
        for c in S:
            if i < len(word) and word[i] == c:
                i += 1
        if i == len(word):
            return word
    return ""

Longest word in dictionary through deleting problem solution in Java.

class Solution {
	public String findLongestWord(String s, List<String> dictionary) {

		String answer = "";
		String temAnwer = "";
		Collections.sort(dictionary);

		for (String vocabulary : dictionary) {
			int pointer = 0;
			int vocabularyLength = vocabulary.length();
			vocabulary.charAt(pointer);

			for (int i = 0; i < s.length(); i++) {

				if (vocabulary.charAt(pointer) == s.charAt(i)) {

					pointer++;

				}

				if (pointer == vocabularyLength) {
					temAnwer = vocabulary;
					break;
				}

			}

			if (temAnwer.length() > answer.length()) {
				answer = temAnwer;
			}

		}

		return answer;
	}
}

Problem solution in C++.

class Solution {
public:
    
    bool isSubsequence(string a, string b) {
        // to check if string b is a subsequence of a
        int ai = 0;
        int bi = 0;
        while(ai < a.length() and bi < b.length()) {
            if(a[ai]==b[bi]) {
                ai++;
                bi++;
            } else {
                ai++;
            }
        }
        if(bi==b.length()) {
            return true;
        } 
        return false;
    }
    
    string findLongestWord(string s, vector<string>& dictionary) {
        string ans = "";
        for(string b: dictionary) {
            if(isSubsequence(s,b)) {
                if(b.size() > ans.size() or (b.size()==ans.size() and b < ans)) {
                    ans = b;
                }
            }
        }
        return ans;
    }
};

Problem solution in C.

#include <string.h>

static int cmp(void *a, void *b) {
	int res = strlen(*(char**)b) - strlen(*(char**)a);
	return res == 0 ? strcmp(*(char**)a, *(char**)b) : res;
}

static int findOneWord(char *s, char *d) {
	for (; *s && *d; s++)
		if (*s ==  *d)
			d++;
	return !*d;
}

char* findLongestWord(char* s, char** d, int dSize) {
	qsort(d, dSize, sizeof(char**), cmp);
	for (; *d; d++)
		if (findOneWord(s, *d))
			return *d;
	return ""; 
}

Leetcode Longest word in dictionary through deleting problem solution

Leetcode Longest word in dictionary through deleting problem solution in Python.

Longest word in dictionary through deleting problem solution in Java.

Problem solution in C++.

Problem solution in C.

Leave a Reply

Pages

Practice