# Easy Java Solution, isSubSequence

• Idea is sort the dictionary `d` first by length `DESC` then lexicographical `ASC` and test if `p` is `SubSequence` of `s`. The first match is the answer.

``````public class Solution {
public String findLongestWord(String s, List<String> d) {
if (s.length() == 0 || d.size() == 0) return "";

Collections.sort(d, (a, b) -> {
if (a.length() != b.length()) return b.length() - a.length();
return a.compareTo(b);
});

for (String p : d) {
if (s.length() < p.length()) continue;
if (isSubSeq(s, p)) return p;
}

return "";
}

private boolean isSubSeq(String s, String p) {
int i = 0, j = 0;
while (i < s.length() && j < p.length()) {
if (s.charAt(i) == p.charAt(j)) {
i++; j++;
}
else {
i++;
}
}
return j == p.length();
}
}
``````

• There is no need to sort the dictionary. We could compare the string with current result during the iteration of the dictionary.

If sorting the dictionary, let N be the size of dictionary, L be the length of each string in the dictionary, Ls be the length of string s, then the time complexity is
`O(NlgN * L + N * Ls) = O(N(lgN*L + Ls))`. (each string comparison will cost O(L) time)
If without sorting, the time complexity is:
`O(N*L + N * Ls) = O(N(L + Ls))`

The following is my code:

``````public class Solution {
public String findLongestWord(String s, List<String> d) {
String res = "";
if (s.length() == 0 || d.size() == 0) {
return res;
}
for (String str : d) {
int resLen = res.length();
int strLen = str.length();
if (isSequence(s, str) &&
(strLen > resLen || (strLen == resLen && str.compareTo(res) < 0))) {
res = str;
}
}
return res;
}

private boolean isSequence(String s, String d) {
int i = 0;
int j = 0;
while (i < s.length() && j < d.length()) {
while (i < s.length() && s.charAt(i) != d.charAt(j)) {
i ++;
}
if (i < s.length()) {
i ++;
j ++;
}
}
return j == d.length();
}
}
``````

• if (a.length() != b.length()) return b.length() - a.length();

Could you please explain this part.

• @AkshathaNayak We want to sort the dictionary `d` first by length `DESC` then lexicographical `ASC`. Thus if `a`'s length does not equal to `b`'s length, then after sort `b` will be in front of `a`.

• @shawngao Thanks!

• ``````private boolean isSubSeq(String s, String p) {
int i = 0, j = 0;
while (i < s.length() && j < p.length()) {
if (s.charAt(i) == p.charAt(j)) {
j++;
}
i++;
}
return j == p.length();
}``````

• @shawngao Nice solution. Here's my very clean solution without sorting. Sorting incurs of runtime complexity of at least klog(k), where k is the number of words in the dictionary. My algorithm has a runtime complexity of nk, where n is the number of characters in s.

``````public class Solution {
public String findLongestWord(String s, List<String> d) {
if (s == null || s.length() == 0 || d == null || d.size() == 0) {
return "";
}

String longest = "";

for (String word : d) {
if (containsSubsequence(s, word) && word.length() >= longest.length()) {
if (word.length() > longest.length() || word.compareTo(longest) < 0) {
longest = word;
}
}
}

return longest;
}

private boolean containsSubsequence(String s, String word) {
int i = 0;
for (char c : s.toCharArray()) {
if (c == word.charAt(i)) {
i ++;
if (i == word.length()) {
return true;
}
}
}
return false;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.