leetcode763：划分字母区间

题目链接

leetcode

题目描述

给你一个字符串 s 。把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

C++ 代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

/*
    因为同一个字母只能出现在同一个片段，
    所以同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。
    因此，遍历字符串得到每个字母最后一次出现的下标位置，之后使用贪心的方法。

    使用贪心的思想，寻找每个片段可能的最小结束下标，保证每个片段的长度一定是符合要求的最短长度。
    若取更短的片段，则一定会出现同一个字母出现在多个片段中的情况。
    由于每次取的片段都是最短的片段，所以得到的片段数也是最多的。

    时间复杂度：O(n)
        其中 n 是字符串的长度，需要遍历字符串两次。
        第一次遍历时记录每个字母最后一次出现的下标位置，
        第二次遍历时进行字符串的划分。
    空间复杂度：O(C)
        其中 C 是字符串中的字符集。
        本题中字符串只包含小写字母，因此 C = 26。
*/
class Solution {
public:
    vector<int> partitionLabels(string s) {
        int length = s.size();
        int lastIndex[26];
        for (int i = 0; i < length; i ++) {
            lastIndex[s[i] - 'a'] = i;
        }

        vector<int> segment;
        int start = 0, end = 0;
        for (int i = 0; i < length; i ++) {
            end = max(end, lastIndex[s[i] - 'a']);
            if (i == end) {
                segment.push_back(end - start + 1);
                start = end + 1;
            }
        }

        return segment;
    }
};

int main() {
    Solution solution;
    vector<string> test_cases = {
        "ababcbacadefegdehijhklij",
        "eccbbbbdec"
    };

    for (const auto& S : test_cases) {
        cout << "Input: " << S << endl;
        cout << "Output: ";
        vector<int> result = solution.partitionLabels(S);
        for (int num : result) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   记录每个字符的最后出现位置：
       使用一个哈希表 last 记录每个字符在字符串中最后出现的位置。
   遍历字符串：
       使用两个指针 start 和 end 来表示当前区间的起始和结束位置。
       遍历字符串时，更新 end 为当前字符的最后出现位置。
       如果当前索引 i 等于 end，说明当前区间结束，
       将区间长度 end - start + 1 添加到结果中，并更新 start 为下一个区间的起始位置。
   返回结果：
       遍历结束后，返回所有区间的长度。

   时间复杂度：O(n)
       遍历字符串两次，时间复杂度为 O(n)，其中 n 是字符串的长度。
   空间复杂度：O(1)
       使用了一个哈希表来记录每个字符的最后出现位置，空间复杂度为 O(1)，
       因为字符集大小是固定的（最多 26 个字母）。
*/
// partitionLabels 将字符串划分为若干个区间，每个区间内的字符互不相同
func partitionLabels(s string) []int {
    // 记录每个字符最后出现的位置
	last := make(map[rune]int)
	for i, c := range s {
		last[c] = i
	}

	var result []int
	start, end := 0, 0

	for i, c := range s {
		end = max(end, last[c]) // 更新当前区间的最远边界
		if i == end {
			// 如果当前索引到达了区间的最远边界，说明一个区间结束
			result = append(result, end - start + 1)
			start = i + 1 // 更新下一个区间的起始位置
		}
	}

	return result
}

func main() {
	// 测试用例
	testCases := []struct {
		s        string
		expected []int
	}{
		{
			s:        "ababcbacadefegdehijhklij",
			expected: []int{9, 7, 8},
		},
		{
			s:        "eccbbbbdec",
			expected: []int{10},
		},
		{
			s:        "a",
			expected: []int{1},
		},
	}

	for i, tc := range testCases {
		result := partitionLabels(tc.s)
		fmt.Printf("Test Case %d, Input: s = %q\n", i+1, tc.s)
		if fmt.Sprint(result) == fmt.Sprint(tc.expected) {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}