题目链接

Longest Word in Dictionary through Deleting - LeetCode

注意点

长度一样的字符串要按字典序返回较小的

解法

解法一：遍历字典中的单词，用一个变量i来记录单词中的某个字母的位置，我们遍历给定字符串，如果遍历到单词中的某个字母来，i自增1，如果没有，就继续往下遍历。这样如果最后i和单词长度相等，说明单词中的所有字母都按顺序出现在了字符串s中。如果能得到，而且单词长度大于等于结果ret的长度，我们再看是否需要更新结果ret，有两种情况是必须要更新结果ret的，一个是当前单词长度大于结果ret的长度，另一种是当前单词长度和ret相同，但是字母顺序小于结果ret，这两种情况下更新结果ret即可

class Solution {

public:

    string findLongestWord(string s, vector<string>& d) {

        string ret = "";

        int i,m,n = d.size();

        for(i = 0;i < n;i++)

        {

            int j = 0;

            m = d[i].size();

            for(char c:s)

            {

                if(j < m && c == d[i][j]) j++;

            }

            if(j == m)

            {

                if(m > ret.size()) ret = d[i];

                else if(m == ret.size() && ret > d[i]) ret = d[i];

            }

        }

        return ret;

    }

};

小结

一开始没看懂题目是什么意思，理解成最长前缀了，其实题目是问能否将s中的某些字母删除而得到字典中的单词

巴特西

Longest Word in Dictionary through Deleting - LeetCode

题目链接

注意点

解法

小结

最新文章

热门文章