Leetcode_524: Longest Word in Dictionary through Deleting

笔记:Leetcode 524 Longest Word in Dictionary through Deleting,分类是sort, two pointer,博主的解法比solution中10行的要快一点,事先对词典进行排序,在词典规模大时,博主解法更有优势。

题目:

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 1:

Input: s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”] Output: “apple”

Example 2:

Input: s = “abpcplea”, d = [“a”,”b”,”c”] Output: “a”

Note:

All the strings in the input will only contain lower-case letters.

The size of the dictionary won’t exceed 1,000.

The length of all the strings in the input won’t exceed 1,000.


解答:

博主的解法,核心判断步骤和大家一样,两个指针分别扫两个字符串,遇到相同就都前进一步,遇到不同就只有字符串部分前进一步。

博主和大家不同的地方在于,博主事先对词典进行排序,使得检测时候不需要遍历整个词典,理论上在词典规模很大的时候博主的算法是更优的,实际上词典规模并没有那么大,最终战胜了88%的c++答案

class Solution {
public:
	static bool compare(const string& a, const string& b){
		return a.length() > b.length();
	}

	bool iscomp(string& s, string& d){
		const int slen = s.length(), dlen = d.length();
		int i = 0, j = 0;
		if (dlen > slen){
			return false;
		}
		for (i = 0; i < dlen;){
			if (s[j] == d[i]){
				i++;
				j++;
				if (i == dlen){
					return true;
				}
			}
			else{
				j++;
			}
			if (j == slen){
				return false;
			}

		}
		return false;
	}

	string findLongestWord(string s, vector<string>& d) {
		if (s == "")
			return string("");

		sort(d.begin(), d.end());
		stable_sort(d.begin(), d.end(), compare);

		const int dsz = d.size();
		for (int j = 0; j < dsz; ++j){
			if (iscomp(s, d[j])){
				return d[j];
			}
		}

		return string("");
	}
};

 

发表评论