LeetCode 521 longest special sequence I
subject
Method: brain sharp turn
The length of the subsequence of a string will not exceed the length of the string. If the length of the subsequence is equal to the length of the string, the subsequence is the string.
-
If the two strings are the same (the same length and content), the subsequence of any string will appear in both strings, and - 1 should be returned
-
If two strings are different
- When the two strings are different in length, you can choose the longer string as the longest special sequence. Obviously, it will not be a subsequence of the shorter string
- When two strings have the same length (but not the same string), you can still choose one of them as the longest special sequence, which will not be a subsequence of the other string
class Solution {
public int findLUSlength(String a, String b) {
if (a.equals(b)) {
return -1;
}
return Math.max(a.length(), b.length());
}
}
-
Time complexity: O ( n ) O(n) O(n)
-
Space complexity: O ( 1 ) O(1) O(1)
equals method of String class:
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = value.length;
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
}
return false;
}
LeetCode 522 longest special sequence II
subject
Method 1: Violence
Generate all subsequences of all strings, store them in HashMap, and record the number of occurrences of each subsequence. Then find the longest subsequence with the number of occurrences of 1. If no such subsequence exists, − 1 is returned.
class Solution {
public int findLUSlength(String[] strs) {
HashMap< String, Integer > map = new HashMap < > ();
for (String s: strs) {
for (int i = 0; i < (1 << s.length()); i++) {
String t = "";
for (int j = 0; j < s.length(); j++) {
// System.out.println("i = " + i + " j = " + j + " (i >> j) = " + (i >> j) + " ((i >> j) & 1) = " + ((i >> j) & 1));
if (((i >> j) & 1) != 0) {
t += s.charAt(j);
}
}
map.put(t, map.getOrDefault(t, 0) +1);
}
}
int res = -1;
for (String s: map.keySet()) {
if (map.get(s) == 1) {
res = Math.max(res, s.length());
}
}
return res;
}
}
- Time complexity: O ( n × 2 x ) O(n \times 2^x) O(n × 2x), where x x x is the average length of all strings, n n n is the number of strings
- Space complexity: O ( n × 2 x ) O(n \times 2^x) O(n×2x)
Method 2: check each string
If there is such a special sequence, it must be a given string.
Check whether each string is a subsequence of other strings:
- If not, it is a special sequence. Finally, the special sequence with the largest length is returned.
- Returns - 1 if no special sequence exists.
class Solution {
// Determine whether x is a subsequence of y
// The subsequence of S can be realized by deleting some characters in the string s
public boolean isSubsequence(String x, String y) {
int j = 0;
for (int i = 0; i < y.length() && j < x.length(); i++) {
if (x.charAt(j) == y.charAt(i)) {
j++;
}
}
return j == x.length();
}
public int findLUSlength(String[] strs) {
int res = -1;
for (int i = 0; i < strs.length; i++) {
int j = 0;
for (j = 0; j < strs.length; j++) {
if (j == i) {
continue ;
}
if (isSubsequence(strs[i], strs[j])) {
break;
}
}
if (j == strs.length) {
res = Math.max(res, strs[i].length());
}
}
return res;
}
}
- Time complexity: O ( x × n 2 ) O(x \times n^2) O(x × n2), where n n n is the number of strings, x x x is the average length of each string
- Space complexity: O ( 1 ) O(1) O(1)