Force deduction solution summary 522- longest special sequence II

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

Given string list  strs , Return to it The longest special sequence . If the longest special sequence does not exist , return -1 .

Special sequence The definition is as follows ： The sequence is a string Unique subsequence （ That is, it cannot be a subsequence of another string ）.

 s  Of   Subsequences can be made by deleting strings  s  Implementation of some characters in .

for example ,"abc"  yes "aebdc"  The subsequence , Because you can delete "aebdc" Use the underscore character in to get "abc" ."aebdc" The subsequence of also includes "aebdc"、 "aeb"  and "" ( An empty string ).
 

Example 1：

Input : strs = ["aba","cdc","eae"]
Output : 3
Example 2:

Input : strs = ["aaa","aaa","aa"]
Output : -1
 

Tips :

2 <= strs.length <= 50
1 <= strs[i].length <= 10
strs[i]  Only lowercase letters

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-uncommon-subsequence-ii
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  First, find out all the duplicates in the string array , What is repeated must not be a unique subsequence .
*  Then sort the string array , Start long , Short traversal .
*  If the current string is repeated , Is added to the set .
*  If not, judge whether it is a subsequence of strings in the set , If not, it is the desired result . If it is , Then skip and continue to find the next .

Code ：

public class Solution522 {

    public int findLUSlength(String[] strs) {
        Set<String> set = new HashSet<>();
        Set<String> repeatSet = new HashSet<>();
        for (String str : strs) {
            if (set.contains(str)) {
                repeatSet.add(str);
            } else {
                set.add(str);
            }
        }
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.length() - o1.length();
            }
        });
        Set<String> checkSet = new HashSet<>();
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            if (repeatSet.contains(str)) {
                checkSet.add(str);
                continue;
            }
            // Judgment is not checkSet The subsequence in 
            if (isChild(checkSet, str)) {
                continue;
            }
            return str.length();
        }
        return -1;
    }

    private boolean isChild(Set<String> checkSet, String str) {
        if (checkSet.size() == 0) {
            return false;
        }
        char[] strChars = str.toCharArray();
        for (String checkStr : checkSet) {
            // Judge str Is it right? checkStr The subsequence 
            char[] checkChars = checkStr.toCharArray();
            int index = 0;
            for (int i = 0; i < checkChars.length; i++) {
                if (strChars[index] == checkChars[i]) {
                    index++;
                }
                if (index == str.length()) {
                    return true;
                }
            }
        }
        return false;
    }

}