본문 바로가기

알고리즘 문제풀이/LeetCode

[LeetCode 763] Partition Labels with Java

leetcode.com/problems/partition-labels/submissions/

 

Partition Labels - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

 

Example 1:

Input: S = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

 

Note:

  • S will have length in range [1, 500].
  • S will consist of lowercase English letters ('a' to 'z') only.
import java.util.*;

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> ans = new LinkedList<>();
        int start = 0;
        int max_index = Integer.MIN_VALUE;
        boolean[] visited = new boolean[26];
        for (int i = 0; i < S.length(); i++){
            char alphabet = S.charAt(i);
            if (!visited[alphabet - 'a']) {
                visited[alphabet - 'a'] = true;
                max_index = Math.max(max_index, S.lastIndexOf(alphabet));
            }
            if (max_index == i){
                ans.add(i - start + 1);
                start = i + 1;
            }
        }
        return ans;
    }
}

1. 어려웠던 점:

- X

 

2. 알게된 점:

- lastIndexOf 활용법

3. 알고리즘 풀이:

알파벳에 대해 방문했는지 안했는지 확인해주는 visited[26] 배열

start 포인터로 부분문자열이 어디서 부터 시작하는지 체크해둔다. (나중에 문자열 길이 계산을 위해)

 

max_index란 현재 부분문자열에 속하는 알파벳들을 확인해서 어디까지 가야하는지 알게해준다.

예를 들어, "abcabd" 라면,

첫 번째 인덱스에서는 a를 확인해 3까지 무조건 가야함을 알 수 있고,

두 번째 인덱스에서는 이미 저장돼있는 max_index인 3과, b의 마지막 인덱스인 4와 비교해 더 큰 값이 4로 변경된다.

 

이미 방문했던 알파벳이면 다시 max_index를 계산할 필요가 없으므로,

visited[26] 배열을 선언해, 방문한 알파벳을 체크해준다.

for문에서 max_index에 도달하게 되면, 부분문자열이 나뉘어진것이므로 길이를 계산해 리스트에 넣어준다.