最长子序列

问题陈述

删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序的最小字符串。

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

Output:
"apple"

算法实现

采用双指针:遍历给定字符串,因为找的是子集,与字典中的字符串一个个比.如果相等,它俩下标都加一,再判断
字典中的字符串是否和下标相等了,如果相等,证明找到了。

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
28
29
30
31
32
class Solution{
    public String findLongestWord(String s,List<String> d){
        char[] sc=s.toCharArray();
        String result="";
        for(String ds:d){
            if(result.length() > ds.length() || (result.length() == ds.length() && result.compareTo(ds) < 0)){
                continue;
            }

            if(isSubStr(sc,ds)){
                result = ds;
            }
        }
        return result;
    }
    public boolean isSubStr(char[] sc,String ds){
        // 字典字符串下标
        int i = 0;
        char[] dsc = ds.toCharArray();
        for(char s : sc){
            if(s == dsc[i]){
                i ++;
                // 如果下标和长度相等,就证明找到了
                if(i == dsc.length){
                    return true;
                }
            }
        }
        // 这还找不到,就证明失败了
        return false;
    }
}