[LeetCode - 3] Longest Substring Without Repeating Characters - Java

문제 설명

 

Longest Substring Without Repeating Characters - LeetCode

 

 

풀이 : Success

소스 코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        else if (s.length() == 1) return 1;

        int result = 0;
        String temp = String.valueOf(s.charAt(0)), nextChar;
        s = s.substring(1);

        while (s.length() > 0) {
            nextChar = String.valueOf(s.charAt(0));
            if (!temp.contains(nextChar)) {
                temp += nextChar;
            }
            else {
                if (temp.substring(temp.length() - 1).equals(nextChar))
                    temp = temp.substring(temp.length() - 1);
                else
                    temp = temp.substring(temp.indexOf(nextChar) + 1) + nextChar;
            }

            s = s.substring(1);

            result = temp.length() > result ? temp.length() : result;

        }

        return result;
    }
}

 

풀이 회고

while 반복문을 통해 주어진 문자열 s의 첫 부분부터 순차적으로 다음 문자(nextChar)와의 포함 관계(반복 사용 유무)를 체크하도록 하였습니다. 이때 반복문이 1사이클 돌 때마다 s의 길이는 1씩 감소하여(첫 번째 문자순으로 삭제) 문자열의 끝에 다달았을 때(주어진 문자열 s의 길이가 0이 될 때) 반복문은 종료됩니다.

또한 temp 문자열 변수를 만들었는데 이 temp 문자열 변수에 반복이 없는 문자열을 저장하도록 하고 while 반복문이 끝날 때까지 result 변수에 최대값 비교(삼항연산자)를 통해 temp 문자열의 길이를 지속적으로 할당해주었습니다. 이 result 값은 문제에서 요구하는 "반복되는 문자가 없는 단어의 최대 길이" 값입니다.

반복문을 순회할 때 temp 문자열과 다음 문자 간 포함 관계에 있지 않다면 반복되지 않는 것으로 생각할 수 있으므로 이를(nextChar) temp 변수에 추가시켜주었습니다.

하지만 다음 문자와 포함관계에 있다면 2가지 경우로 나누어 볼 수 있었는데, 우선 temp 변수 끝 문자와 해당 문자가 같다면 temp 변수에는 temp 변수 문자열의 끝 문자(= nextChar)만 할당하도록 했습니다. 이는 기존 temp 문자열에 nextChar을 추가로 할당하게 되면 중복되는 단어가 발생하기 때문입니다.

반대로 temp 변수 끝 문자와 해당 문자가 같지 않다면 temp 변수에는 temp 문자열에서 해당 문자(다음 문자)가 발견된 지점부터 temp 문자열 끝까지(temp.substring(temp.indexOf(nextChar) + 1) 그리고 해당 문자를 다시 더하여 할당하였습니다.

최종적으로 반복문을 모두 돌고 나면 주어진 문자열 s의 길이는 0이 되며(모든 경우의 수 확인 완료) result 변수에는 문제에서 요구하는 "반복되는 문자가 없는 단어의 최대 길이" 값이 할당되게 됩니다.

 

 

 

참고자료

• https://leetcode.com/problems/longest-substring-without-repeating-characters/