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:

1
2
3
4
5
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"

Example 2:

1
2
3
4
5
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.

分析

给定一个字符串以及一个字符串的列表，要求找到列表中最长的一个单词，这个单词可以通过字符串删除某些字符得到，如果有长度一样的单词，按照字母序进行选择。

这道题可以通过自定义排序方法的 compare 接口实现，优先比较单词长度，更长的排在前面，其次比较字母序，按照 ASCII 码进行排列。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public String findLongestWord(String s, List<String> d) {
        Collections.sort(d, new Comparator <String>() {
            public int compare(String s1, String s2) {
                return s2.length() != s1.length() ? s2.length() - s1.length() : s1.compareTo(s2);    
            }
        });
        
        for (String str: d) {
            if (xIsSubStrY(str, s)) {
                return str;
            }
        }
        return "";
    }
    
    private boolean xIsSubStrY(String x, String y) {
        int j = 0;
        for (int i = 0; i < y.length() && j < x.length(); i++) {
            if (x.charAt(j) == y.charAt(i)) {
                j++;
            }
        }
        return j == x.length();
    }
}

相关问题

题目来源