美文网首页算法练习
通过删除字母匹配到字典里最长单词(LeetCode 524)

通过删除字母匹配到字典里最长单词(LeetCode 524)

作者: 倚剑赏雪 | 来源:发表于2020-02-19 20:25 被阅读0次

    题目

    给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个,返回长度最长且字典顺序最小的字符串。如果答案不存在,则返回空字符串。

    示例 1:

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

    输出:
    "apple"

    示例 2:

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

    输出:
    "a"

    说明:

    所有输入的字符串只包含小写字母。
    字典的大小不会超过 1000。
    所有输入的字符串长度不会超过 1000。
    

    解析

    1.依次从d中取出字符,并与s进行对比,若d[i][m] == s[n]则继续遍历,否则,n++;直到m == d[i].Length,若m < d[i].Length说明不是合法字串
    2.此时判断是不是最长字符串,若是则替换,若不是,则继续遍历
    3.若两个字串长度相等,则对比字符串的字符大小

    public string FindLongestWord(string s, IList<string> d) {
            string longStr = "";
            int longLen = -1;
            for (int i = 0; i < d.Count; i++)
            {
                string temp = d[i];
                int m = 0, n = 0;
                while (m < s.Length && n < temp.Length)
                {
                    if (s[m] == temp[n]) n++;
                    m++;
                }
                //d[i]到了最后一个字符,则说明,d[i]是s删除某些字符后的一个字串
                if (n == temp.Length)
                {
                    if (n > longLen)
                    {
                        longLen = n;
                        longStr = temp; 
                    }
                    else if(longLen == n)
                    {
                        longStr = CompareStr(longStr, temp);
                    }
                }
            }
            return longStr;
        }
    
        string CompareStr(string a, string b)
        {
            int i = 0;
            while (i < a.Length)
            {
                if (a[i] - '0' < b[i] - '0') return a;
                return b;
            }
    
            return "";
        }
    
    

    相关文章

      网友评论

        本文标题:通过删除字母匹配到字典里最长单词(LeetCode 524)

        本文链接:https://www.haomeiwen.com/subject/psdzfhtx.html