Giả sử chúng ta có một chuỗi S gồm các chữ cái thường. Chúng tôi sẽ phân vùng chuỗi này thành nhiều phần nhất có thể để mỗi chữ cái xuất hiện ở nhiều nhất một phần, cuối cùng trả về một danh sách các số nguyên đại diện cho kích thước của các phần này. Vì vậy, nếu chuỗi giống như “ababcbacadefegdehijhklij”, đầu ra là [9,7,8], bởi vì các phân vùng là “ababcbaca”, “defegde”, “hijhklij”. Vì vậy, đây là một phân vùng để mỗi chữ cái xuất hiện trong nhiều nhất một phần. Một phân vùng như "ababcbacadefegde", "hijhklij" là không đúng, vì nó chia S thành ít phần hơn.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- xác định một bản đồ được gọi là cnt
- cho tôi trong phạm vi từ 0 đến s, cnt [s [i]]:=i
- j:=0, start:=0 and i:=0 and n:=size of s
- xác định ans một mảng
- trong khi tôi
- j:=max of j và cnt [s [i]]
- nếu i =j, sau đó chèn i - start + 1 vào ans và bắt đầu:=i + 1
- tăng tôi lên 1
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> partitionLabels(string s) {
map <char, int> cnt;
for(int i = 0; i < s.size(); i++)cnt[s[i]] = i;
int j = 0, start = 0;
int i = 0;
int n = s.size();
vector <int> ans;
while(i < n){
j = max(j, cnt[s[i]]);
if( i == j){
ans.push_back(i-start+ 1);
start = i + 1;
}
i++;
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
} Đầu vào
"ababcbacadefegdehijhklij"
Đầu ra
[9,7,8]