BiruLyu
6/28/2017 - 9:04 PM

## 522. Longest Uncommon Subsequence II(2nd).java

``````public class Solution {
public int findLUSlength(String[] strs) {
Arrays.sort(strs, new Comparator<String>(){
public int compare(String a, String b) {
return b.length() - a.length();
}
});
int len = strs.length;
for(int i = 0; i < len; i++){
boolean isFound = true;
for(int j = 0; j < len; j++){
if (i != j) {
if (isSubSequence(strs[i], strs[j])) {
isFound = false;
break;
}
if (strs[i].length() > strs[i].length()) {
break;
}
}

}
if (isFound) return strs[i].length();
}
return -1;
}

private boolean isSubSequence(String a, String b) {
int lenA = a.length();
int lenB = b.length();
if (lenA > lenB) return false;
if (lenA == lenB) return a.equals(b);
int idx = 0;
for (char c : b.toCharArray()) {
if (idx < lenA && c == a.charAt(idx)) {
idx++;
}
}
return idx == lenA;

}
}``````
``````public class Solution {
public int findLUSlength(String[] strs) {
int maxLen;
Map<String, Integer> map = new HashMap<String, Integer>();
for (String str : strs) {
for (String seq : getSubSequence(str)) {
map.put(seq, map.getOrDefault(seq, 0) + 1);
}

}
int res = -1;
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1) {
res = Math.max(res, entry.getKey().length());
}
}
return res;
}

public Set<String> getSubSequence(String str) {
Set<String> set = new HashSet<String>();
if (str.length() == 0) {
return set;
}
Set<String> temp = getSubSequence(str.substring(1));
for (String seq : temp) {
}
return set;
}
}``````
``````public class Solution {
// https://discuss.leetcode.com/topic/85044/python-simple-explanation
public int findLUSlength(String[] strs) {
Arrays.sort(strs, new Comparator<String>() {
public int compare(String s1, String s2) {
return s2.length() - s1.length();
}
});
int n = strs.length;
for (int i = 0; i < n; i++) {
String s1 = strs[i];
boolean isFound = true;
for (int j = 0; j < n; j++) {
if (i != j && isSubSequence(s1, strs[j])) {
isFound = false;
break;
}
}
if (isFound) {
return s1.length();
}
}
return -1;
}
private boolean isSubSequence(String s1, String s2) {
if (s1.length() > s2.length()) return false;
if (s1.length() == s2.length()) return s1.equals(s2);
int index = 0;
for (char c : s2.toCharArray()) {
if (index < s1.length() && c == s1.charAt(index)) {
index++;
}
}
return index == s1.length();
}
}``````
``````class Comparator1 implements Comparator<String>{
public int compare(String a, String b){
return -a.length() + b.length();
}
}
public class Solution {
public int findLUSlength(String[] strs) {
Arrays.sort(strs, new Comparator1());
for(int i = 0; i < strs.length; i++){
String s = strs[i];
int j = 0;
for(j = 0; j < strs.length; j++){
if(j==i) continue;
String t = strs[j];
if(s.length()> t.length()){
return s.length();
}else if(s.length()== t.length()){
if(s.equals(t)) break;
}else {
if(isSubstring(t, s)) break;
}
}
if(j == strs.length) return s.length();
}
return -1;
}

public boolean isSubstring(String org, String sub){
int idx = 0;
for(int i = 0; i < sub.length(); i++){
char c = sub.charAt(i);
while(idx<org.length() && org.charAt(idx)!=c) idx++;
if(idx==org.length()) return false;
idx++;
}
return true;
}
}``````