Li Kou today's question -522 Longest special sequence

522. The longest special sequence II

Ideas ： Subsequence , It's not a string , So there is no need to pay attention to whether it is continuous .s The special sequence of can he delete the string s Implementation of some characters in .

Topic translation ： Give an array of strings , Find the string inside to satisfy The current string is not a subsequence of other strings in the string array , Returns the string that meets the condition The length of the longest string

Use a double loop , The outer layer enumerates each string str[i] As a special sequence , The inner layer enumerates each string str[j] (i != j), Judge str[i] If not for str[j] Subsequence of .

Judge str[i] Whether it is str[j] The subsequence , You can use the double pointer method . Initial pointer pi and pj Points to the first character of two strings , If two characters are the same , Then both pointers move one position to the right , Indicates that the match is successful , Otherwise, just move to the right pj, Indicates that the match failed . If pi After traversing the entire string , Just explain str[i] yes str [j] The subsequence .

In all satisfied str[i] in , Choose the longest one , Return the length as the answer , If it doesn't exist, return -1

class Solution {
    
    public int findLUSlength(String[] strs) {
    
        int n = strs.length;
        int ans = -1;
        for (int i = 0; i < n; ++i) {
    
            // Set a flag 
            boolean check = true;
            for (int j = 0; j < n; ++j) {
    
                // As long as it is found in other strings that it is a subsequence , Then mark it as false, Exit loop 
                if (i != j && is_son(strs[i], strs[j])) {
    
                    check = false;
                    break;
                }
            }
            // In all the “ orphan ” Find the longest one in , Assign a value to ans.
            if (check) {
    
                ans = Math.max(ans, strs[i].length());
            }
        }
        return ans;
    }

    public boolean is_son(String s, String t) {
    
       	// Define two pointers 
        int ptS = 0, ptT = 0;
        while (ptS < s.length() && ptT < t.length()) {
    
            if (s.charAt(ptS) == t.charAt(ptT)) {
    
                ++ptS;
            }
            ++ptT;
        }
        // Back to Shanghai true perhaps false  If you wait , Then return to true
        return ptS == s.length();
    }
}

Actually, reading comprehension questions , It will not be so difficult .