[LeetCode] Longest Word in Dictionary through Deleting

Problem: Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"

Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"

Approach: If you see it is a problem of finding if a string is a subsequence of another string as we are just allowed to delete the characters from the string. Now basically we iterate through all the strings in the dictionary "d" and whenever we find that a string in d is a subsequence of s, we look for max length and max length string(our output) and then we just update these max variables accordingly.

That's all!

Implementation in C#:

        public string FindLongestWord(string s, IList<string> d)

        {

            int maxLength = 0;

            string maxLengthStr = string.Empty;

            for (int i = 0; i < d.Count; ++i)

            {

                string currStr = d[i];

                if (this.IsSubSequence(s, currStr))

                {

                    if (maxLength < currStr.Length)

                    {

                        maxLength = currStr.Length;

                        maxLengthStr = currStr;

                    }

                    else if (maxLength == currStr.Length)

                    {

                        if (string.Compare(currStr, maxLengthStr) < 0)

                        {

                            maxLengthStr = currStr;

                        }

                    }

                }

            }

            return maxLengthStr;

        }

        public bool IsSubSequence(string sequence, string str)

        {

            int currSeqIndex = 0, currStrIndex = 0;

            while (currSeqIndex < sequence.Length && currStrIndex < str.Length)

            {

                if (sequence[currSeqIndex] == str[currStrIndex])

                {

                    ++currStrIndex;

                }

                ++currSeqIndex;

            }

            return currStrIndex == str.Length;

        }

Complexity: O(n * l) where n is number of strings in d and l is length of the longest string in d.