문제 설명 :

문자열 strs의 배열이 주어지면 그들 사이에서 가장 긴 흔하지 않은 하위 시퀀스의 길이를 반환합니다. 가장 긴 흔하지 않은 하위 시퀀스가 ​​없으면 -1을 반환합니다.

문자열 배열 사이의 흔하지 않은 하위 시퀀스는 한 문자열의 하위 시퀀스이지만 다른 문자열은 그렇지 않은 문자열입니다.

문자열 s의 하위 시퀀스는 s에서 임의 개수의 문자를 삭제한 후 얻을 수 있는 문자열입니다.

예를 들어 "abc"는 "aebdc"에서 밑줄 친 문자를 삭제하여 "abc"를 얻을 수 있기 때문에 "aebdc"의 하위 시퀀스입니다. "aebdc"의 다른 하위 시퀀스에는 "aebdc", "aeb"및 ""(빈 문자열)이 포함됩니다.

테스트 사례:

예 1:

입력: strs = ["aba","cdc","eae"]
출력: 3

예 2:

입력: strs = ["aaa","aaa","aa"]
출력: -1

제약 조건:

1 <= 문자열 길이 <= 50
1 <= 문자열[i].길이 <= 10
strs[i]는 영문 소문자로 구성됩니다.

접근하다 :

1) 각 문자열 길이를 기준으로 문자열 배열을 역순으로 정렬합니다.
Arrays.sort(strs, (s1, s2) -> Integer.compare(s2.length(), s1.length()));
2) 그런 다음 어레이 내부에 존재하는 중복 항목을 찾습니다. 중복이 없으면 응답은 가장 큰 문자열의 길이가 됩니다.

public Set<String> findDuplicate(String [] strs) {
        Set<String> store = new HashSet<>();
        Set<String> duplicate = new HashSet<>();
        for (String s : strs) {
            if (store.contains(s)) {
                duplicate.add(s);
            }
            else {
                store.add(s);
            }
        }
        return duplicate;
    }

3) 이제 중복되지 않은 다른 문자열을 확인하고 하위 시퀀스인 것을 건너뜁니다.

4) 문자열이 중복되지 않고 i == 0이면 해당 문자열 길이가 우리가 찾는 답입니다.

5) 그렇지 않으면 이 문자열을 다른 문자열과 함께 확인하고 하위 시퀀스인지 확인합니다. 하위 시퀀스인 경우 건너뛰고 그렇지 않은 경우 j == i - 1이면 해당 문자열 길이가 답이 됩니다.

for (int i=0; i<strs.length; i++) {
            if (!duplicates.contains(strs[i])) {
                if (i == 0)
                    return strs[i].length();
                for (int j=0; j<i; j++) {
                    if (isSubsequence(strs[j], strs[i]))
                        break;
                    if (j == i - 1)
                        return strs[i].length();
                }
            }
        }
        return -1;
    }

    public boolean isSubsequence(String s1, String s2) {
        int i = 0;
        int j = 0;
        while (i < s1.length() && j < s2.length()) {
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == s2.length();
    }

최종 코드:

class Solution {
    public int findLUSlength(String[] strs) {
        if (strs == null || strs.length == 0)
            return -1;
        // 1. sort in reversing order
        Arrays.sort(strs, (s1, s2) -> Integer.compare(s2.length(), s1.length()));
        // 2. Find the duplicates if any
        // if no duplicates then the longest string is the answer
        Set<String> duplicates = findDuplicate(strs);
        if (duplicates.size() == 0) {
            return strs[0].length();
        }
        // check for other strings that are not duplicate
        // skip which are common
        for (int i=0; i<strs.length; i++) {
            if (!duplicates.contains(strs[i])) {
                if (i == 0)
                    return strs[i].length();
                for (int j=0; j<i; j++) {
                    if (isSubsequence(strs[j], strs[i]))
                        break;
                    if (j == i - 1)
                        return strs[i].length();
                }
            }
        }
        return -1;
    }

    public boolean isSubsequence(String s1, String s2) {
        int i = 0;
        int j = 0;
        while (i < s1.length() && j < s2.length()) {
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == s2.length();
    }

    public Set<String> findDuplicate(String [] strs) {
        Set<String> store = new HashSet<>();
        Set<String> duplicate = new HashSet<>();
        for (String s : strs) {
            if (store.contains(s)) {
                duplicate.add(s);
            }
            else {
                store.add(s);
            }
        }
        return duplicate;
    }
}

시간 및 공간 복잡성:

시간 - O(n ^ 2) 여기서 n은 배열의 길이입니다

.

중복 항목을 기록하기 위해 추가 세트를 사용하는 공간 - O(n)

Rohithv07 / LeetCode

해결된 LeetCode 문제.

LeetCode

해결된 LeetCode 문제.



View on GitHub