C ++中的分区标签

假设我们给出了一个小写字母的字符串S。我们将这个字符串分成尽可能多的部分，以便每个字母最多显示一个部分，最后返回代表这些部分大小的整数列表。因此，如果字符串类似于“ ababcbacadefegdehijhklij”，则输出为[9,7,8]，因为分区是“ ababcbaca”，“ defegde”，“ hijhklij”。因此，这是一个分区，以便每个字母最多出现一个部分。像“ ababcbacadefegde”，“ hijhklij”之类的分区是不正确的，因为它将S分成更少的部分。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个称为cnt的映射

• 对于范围在0到s之间的i，cnt [s [i]]：= i

• j：= 0，开始：= 0且i：= 0和n：= s的大小

• 定义一个数组ans

• 当我<n

• j：= j和cnt [s [i]]的最大值

• 如果i = j，则将i – start + 1插入ans并开始：= i + 1

• 使我增加1

• 返回ans

例子（C ++）

让我们看下面的实现以更好地理解-

#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"));
}

输入值

"ababcbacadefegdehijhklij"

输出结果

[9,7,8]