题解 | #最长特殊子序列（二）#

import java.util.*;

/**
 * NC411 最长特殊子序列（二）
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param strs string字符串ArrayList 
     * @return int整型
     */
    public int longestUniqueSubsequence (ArrayList<String> strs) {
        return solution(strs);
    }

    /**
     * 贪心
     * @param strs
     * @return
     */
    private int solution(ArrayList<String> strs){
        int n = strs.size();

        // 排序
        // Collections.sort(strs, (o1, o2) -> (o2.length()-o1.length()));
        // 此种方式 似乎 效率更高
        Collections.sort(strs, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2){
                return o2.length()-o1.length();
            }
        });

        // 哈希
        HashMap<String, Integer> map = new HashMap<>();
        for(String str: strs){
            map.put(str, map.getOrDefault(str, 0)+1);
        }

        String key;
        // 贪心
        for(int i=0; i<n; i++){
            key = strs.get(i);
            // 当前字符串 只有唯一一个
            if(map.get(key) == 1){
                // 不是前面字符串的子序列
                if(!isSubSeq(strs, i)){
                    return key.length();
                }
            }
        }

        return -1;
    }

    /**
     * 判断是否为前面字符串的子序列
     * @param strs
     * @param idx
     * @return
     */
    private boolean isSubSeq(ArrayList<String> strs, int idx){
        String sub = strs.get(idx);
        int subLen = sub.length();

        String str;
        int strLen;
        int cnt;
        for(int i=0; i<idx; i++){
            str = strs.get(i);
            strLen = str.length();
            // 长度相等 肯定不是子序列
            if(strLen > subLen){
                cnt = 0;
                // 双指针
                for(int j=0,k=0; j<strLen&&k<subLen; j++){
                    if(str.charAt(j) == sub.charAt(k)){
                        k++;
                        cnt++;
                    }
                }
                if(cnt == subLen){
                    return true;
                }
            }
        }

        return false;
    }
}