Array
Two Pointers
String
Sorting
Description
Given a string s
and a string array dictionary
, return the longest string in the dictionary that can be formed by deleting some of the given string characters . If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:
Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"
Example 2:
Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"
Constraints:
1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s
and dictionary[i]
consist of lowercase English letters.
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
def findLongestWord ( self , s : str , dictionary : List [ str ]) -> str :
def check ( a , b ):
m , n = len ( a ), len ( b )
i = j = 0
while i < m and j < n :
if a [ i ] == b [ j ]:
j += 1
i += 1
return j == n
ans = ''
for a in dictionary :
if check ( s , a ) and ( len ( ans ) < len ( a ) or ( len ( ans ) == len ( a ) and ans > a )):
ans = a
return ans
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 class Solution {
public String findLongestWord ( String s , List < String > dictionary ) {
String ans = "" ;
for ( String a : dictionary ) {
if ( check ( s , a )
&& ( ans . length () < a . length ()
|| ( ans . length () == a . length () && a . compareTo ( ans ) < 0 ))) {
ans = a ;
}
}
return ans ;
}
private boolean check ( String a , String b ) {
int m = a . length (), n = b . length ();
int i = 0 , j = 0 ;
while ( i < m && j < n ) {
if ( a . charAt ( i ) == b . charAt ( j )) {
++ j ;
}
++ i ;
}
return j == n ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public :
string findLongestWord ( string s , vector < string >& dictionary ) {
string ans = "" ;
for ( string & a : dictionary )
if ( check ( s , a ) && ( ans . size () < a . size () || ( ans . size () == a . size () && a < ans )))
ans = a ;
return ans ;
}
bool check ( string & a , string & b ) {
int m = a . size (), n = b . size ();
int i = 0 , j = 0 ;
while ( i < m && j < n ) {
if ( a [ i ] == b [ j ]) ++ j ;
++ i ;
}
return j == n ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 func findLongestWord ( s string , dictionary [] string ) string {
ans := ""
check := func ( a , b string ) bool {
m , n := len ( a ), len ( b )
i , j := 0 , 0
for i < m && j < n {
if a [ i ] == b [ j ] {
j ++
}
i ++
}
return j == n
}
for _ , a := range dictionary {
if check ( s , a ) && ( len ( ans ) < len ( a ) || ( len ( ans ) == len ( a ) && a < ans )) {
ans = a
}
}
return ans
}
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
27 function findLongestWord ( s : string , dictionary : string []) : string {
dictionary . sort (( a , b ) => {
if ( a . length === b . length ) {
return b < a ? 1 : - 1 ;
}
return b . length - a . length ;
});
const n = s . length ;
for ( const target of dictionary ) {
const m = target . length ;
if ( m > n ) {
continue ;
}
let i = 0 ;
let j = 0 ;
while ( i < n && j < m ) {
if ( s [ i ] === target [ j ]) {
j ++ ;
}
i ++ ;
}
if ( j === m ) {
return target ;
}
}
return '' ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 impl Solution {
pub fn find_longest_word ( s : String , mut dictionary : Vec < String > ) -> String {
dictionary . sort_unstable_by ( | a , b | ( b . len (), a ). cmp ( & ( a . len (), b )));
for target in dictionary {
let target : Vec < char > = target . chars (). collect ();
let n = target . len ();
let mut i = 0 ;
for c in s . chars () {
if i == n {
break ;
}
if c == target [ i ] {
i += 1 ;
}
}
if i == n {
return target . iter (). collect ();
}
}
String :: new ()
}
}
GitHub