Longest Word in Dictionary through Deleting-K6K4.com

原题： https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/description/

题意： 给定字符串s和字典d，判断s删去一部分字符是否可以组成的d中的字符串。若可以，求长度最长且字典序最小的字符串。否则返回空串。

约定：（1）所有字符串输入只包含小写字母；（2）字典长度不超过1000；（3）所有字符串长度不超过1000。

例子：

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

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

标签： abpcplea、deleting、字典、longest、dictionary、面试

猜你感兴趣的圈子：

LeetCode交流圈

SLPH

2017-08-12 15:15:26 1楼#1层

Python：贪心算法 + 广度优先搜索

class Solution(object):
    def findLongestWord(self, s, d):
        """
        :type s: str
        :type d: List[str]
        :rtype: str
        """
        ans = []
        dmap = collections.defaultdict(list)
        for w in d:
            dmap[w[0]].append((0, w))
        for c in s:
            wlist = dmap[c]
            del dmap[c]
            for i, w in wlist:
                if i + 1 == len(w):
                    ans.append(w)
                else:
                    dmap[w[i + 1]].append((i + 1, w))
        if not ans: return ''
        maxl = len(max(ans, key = len))
        return min(w for w in ans if len(w) == maxl)

SLPH

2017-08-12 15:16:19 2楼#1层

C++解法一：

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        sort(d.begin(), d.end(), [](string a, string b){
            if (a.size() == b.size()) return a < b;
            return a.size() > b.size();
        });
        for (string str : d) {
            int i = 0;
            for (char c : s) {
                if (i < str.size() && c == str[i]) ++i;
            }
            if (i == str.size()) return str;
        }
        return "";
    }
};

SLPH

2017-08-12 15:16:40 3楼#1层

C++解法二：

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        string res = "";
        for (string str : d) {
            int i = 0;
            for (char c : s) {
                if (i < str.size() && c == str[i]) ++i;
            }
            if (i == str.size() && str.size() >= res.size()) {
                if (str.size() > res.size() || str < res) {
                    res = str;
                }
            }
        }
        return res;
    }
};

取消

回复

推荐圈子

LeetCode交流圈