[LeetCode] 763. Partition Labels - 문제풀이

Description

문자열을 가능한 한 많은 부분으로 분할하여 각 문자가 한 부분에만 표시되도록 나눈 뒤 해당 인덱스를 반환하는 문제입니다.

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

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.

Example 2:

Input: s = "eccbbbbdec"
Output: [10]

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Solution 1. Greedy + Hash Table

public List<Integer> partitionLabels(String s) {
    if(s == null ||s.length() == 0){
        return null;
    }
    List<Integer> result = new ArrayList<>();
    int[] map = new int[26];

    for(int i = 0; i < s.length(); i++){
        map[s.charAt(i)-'a'] = i;
    }

    int last = 0;
    int start = 0;
    for(int i = 0; i < s.length(); i++){
        last = Math.max(last, map[s.charAt(i)-'a']);
        if(last == i){
            result.add(last - start + 1);
            start = last + 1;
        }
    }
    return result;

}

Array을 HashTable로 이용하여 각 배열의 숫자를 기록한 뒤 배열을 진행해 나가며 현재위치와 알파벳의 거리를 계산해 나갑니다. 가장 큰 거리에 안쪽에 요소들이 포함되면 계속 진행시키고 i가 마지막 거리와 같아질 경우 해당 값을 저장하고 다음위치부터 다시 계산해 나갑니다.

Reference

Partition Labels - LeetCode