522. Longest Uncommon Subsequence II

Description

Given an array of strings strs, return the length of the longest uncommon subsequence between them. If the longest uncommon subsequence does not exist, return -1.

An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.

A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.

  • For example, "abc" is a subsequence of "aebdc" because you can delete the underlined characters in "aebdc" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 2 <= strs.length <= 50
  • 1 <= strs[i].length <= 10
  • strs[i] consists of lowercase English letters.

Solutions

Solution 1

Python Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def check(a, b):
            i = j = 0
            while i < len(a) and j < len(b):
                if a[i] == b[j]:
                    j += 1
                i += 1
            return j == len(b)

        n = len(strs)
        ans = -1

        for i in range(n):
            j = 0
            while j < n:
                if i == j or not check(strs[j], strs[i]):
                    j += 1
                else:
                    break
            if j == n:
                ans = max(ans, len(strs[i]))
        return ans

Java Code
 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

class Solution {
    public int findLUSlength(String[] strs) {
        int ans = -1;
        for (int i = 0, j = 0, n = strs.length; i < n; ++i) {
            for (j = 0; j < n; ++j) {
                if (i == j) {
                    continue;
                }
                if (check(strs[j], strs[i])) {
                    break;
                }
            }
            if (j == n) {
                ans = Math.max(ans, strs[i].length());
            }
        }
        return ans;
    }

    private boolean check(String a, String b) {
        int j = 0;
        for (int i = 0; i < a.length() && j < b.length(); ++i) {
            if (a.charAt(i) == b.charAt(j)) {
                ++j;
            }
        }
        return j == b.length();
    }
}

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        int ans = -1;
        for (int i = 0, j = 0, n = strs.size(); i < n; ++i) {
            for (j = 0; j < n; ++j) {
                if (i == j) continue;
                if (check(strs[j], strs[i])) break;
            }
            if (j == n) ans = max(ans, (int) strs[i].size());
        }
        return ans;
    }

    bool check(string a, string b) {
        int j = 0;
        for (int i = 0; i < a.size() && j < b.size(); ++i)
            if (a[i] == b[j]) ++j;
        return j == b.size();
    }
};

Go Code
 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

func findLUSlength(strs []string) int {
	check := func(a, b string) bool {
		j := 0
		for i := 0; i < len(a) && j < len(b); i++ {
			if a[i] == b[j] {
				j++
			}
		}
		return j == len(b)
	}

	ans := -1
	for i, j, n := 0, 0, len(strs); i < n; i++ {
		for j = 0; j < n; j++ {
			if i == j {
				continue
			}
			if check(strs[j], strs[i]) {
				break
			}
		}
		if j == n && ans < len(strs[i]) {
			ans = len(strs[i])
		}
	}
	return ans
}