Leetcode 763. Partition Labels

Tyan

发布于 2019-05-25 23:26:57

3290

发布于 2019-05-25 23:26:57

文章被收录于专栏：SnailTyanSnailTyan

文章作者：Tyan

博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

Version 1

class Solution {
public:
    vector<int> partitionLabels(string S) {
        unordered_map<char, int> m;
        vector<int> result;
        vector<int> indices(S.length());
        for(int i = 0; i < S.length(); i++) {
            m[S[i]] = i;
        }
        for(int i = 0; i < S.length(); i++) {
            indices[i] = m[S[i]];
        }
        int max = 0;
        int start = 0;
        for(int i = 0; i < S.length(); i++) {
            if(indices[i] > max) {
                max = indices[i];
            }
            if(i == max) {
                result.push_back(max - start + 1);
                start = i + 1;
                max = 0;
            }
        }
        return result;
    }
};

Version 2

class Solution {
public:
    vector<int> partitionLabels(string S) {
        unordered_map<char, int> m;
        vector<int> result;
        for(int i = 0; i < S.length(); i++) {
            m[S[i]] = i;
        }
        int max = 0;
        int start = 0;
        for(int i = 0; i < S.length(); i++) {
            if(m[S[i]] > max) {
                max = m[S[i]];
            }
            if(i == max) {
                result.push_back(max - start + 1);
                start = i + 1;
                max = 0;
            }
        }
        return result;
    }
};