leetcode.com/problems/partition-labels/submissions/
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에 도달하게 되면, 부분문자열이 나뉘어진것이므로 길이를 계산해 리스트에 넣어준다.
'알고리즘 문제풀이 > LeetCode' 카테고리의 다른 글
[LeetCode 53] Maximum Subarray with JAVA (0) | 2021.05.11 |
---|---|
[LeetCode 55] Jump Game with JAVA (0) | 2021.05.08 |
[LeetCode 104] Maximum Depth of Binary Tree with JAVA (0) | 2021.04.25 |
[LeetCode 200] Numbers of Islands with JAVA (0) | 2021.04.25 |
[LeetCode 114] flatten-binary-tree-to-linked-list with JAVA (0) | 2021.04.17 |