LeetCode 524. Longest Word in Dictionary through Deleting

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/03/18/LeetCode-524-Longest-Word-in-Dictionary-through-Deleting/

访问原文「LeetCode 524. Longest Word in Dictionary through Deleting」

题目要求

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:

1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won’t exceed 1,000.
3. The length of all the strings in the input won’t exceed 1,000.

题意解析

给出一个String A和一个String数组，在String数组中找到最长的String B，这个String可以满足从A中删除一些字母得到。如果满足的字符串有多个，则选择字母序最小的字符串。

解法分析

将String数组按照长度由大到小、字母序由小到大进行排序，然后顺序寻找满足要求的字符串就可以了。

解题代码

	public String findLongestWord(String s, List<String> d) {
	char[] charNumber = new char[s.length()];
	for (int i = 0; i < s.length(); i++) {
		charNumber[i] = s.charAt(i);
	}

	Collections.sort(d, new Comparator<String>() {

		@Override
		public int compare(String o1, String o2) {
			if (o1.length() != o2.length()) {
				return o2.length() - o1.length();
			}
			return o1.compareTo(o2);
		}

	});

	for (String str : d) {
		int i = 0;
		int j = 0;
		for (; i < str.length(); i++) {
			for(; j < charNumber.length; j++){
				if(str.charAt(i) == charNumber[j]){
					j++;
					if(i == str.length() - 1){
						return str;
					}
					break;
				}
			}
		}
	}

	return "";
}