LeetCode 763 划分字母区间

it2025-06-20 9

刷题日期： 2020年10月22日 00：50

题目描述

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

示例

输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8] 解释：划分结果为 “ababcbaca”, “defegde”, “hijhklij”。每个字母最多出现在一个片段中。像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。 S只包含小写字母 ‘a’ 到 ‘z’ 。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/partition-labels 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

###　贪心

一开始想用贪心的方式去解决这个问题，后来绘制出过程图发现，其分割是固定的。初次分割，必须是根据首字母对整个字符串分割成两半，分别为L_left和L_right。后续是一样的分割方式。直到最后无法分割为止。此时：从左到右，所有叶子节点对应的字符串的长度组成的List即为所求。初始 #mermaid-svg-KGtbiTrmQaZPeQC7 .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .label text{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .node rect,#mermaid-svg-KGtbiTrmQaZPeQC7 .node circle,#mermaid-svg-KGtbiTrmQaZPeQC7 .node ellipse,#mermaid-svg-KGtbiTrmQaZPeQC7 .node polygon,#mermaid-svg-KGtbiTrmQaZPeQC7 .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-KGtbiTrmQaZPeQC7 .node .label{text-align:center;fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .node.clickable{cursor:pointer}#mermaid-svg-KGtbiTrmQaZPeQC7 .arrowheadPath{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-KGtbiTrmQaZPeQC7 .flowchart-link{stroke:#333;fill:none}#mermaid-svg-KGtbiTrmQaZPeQC7 .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-KGtbiTrmQaZPeQC7 .edgeLabel rect{opacity:0.9}#mermaid-svg-KGtbiTrmQaZPeQC7 .edgeLabel span{color:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-KGtbiTrmQaZPeQC7 .cluster text{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-KGtbiTrmQaZPeQC7 .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-KGtbiTrmQaZPeQC7 text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-KGtbiTrmQaZPeQC7 .actor-line{stroke:grey}#mermaid-svg-KGtbiTrmQaZPeQC7 .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .sequenceNumber{fill:#fff}#mermaid-svg-KGtbiTrmQaZPeQC7 #sequencenumber{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 #crosshead path{fill:#333;stroke:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .messageText{fill:#333;stroke:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-KGtbiTrmQaZPeQC7 .labelText,#mermaid-svg-KGtbiTrmQaZPeQC7 .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-KGtbiTrmQaZPeQC7 .loopText,#mermaid-svg-KGtbiTrmQaZPeQC7 .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-KGtbiTrmQaZPeQC7 .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-KGtbiTrmQaZPeQC7 .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-KGtbiTrmQaZPeQC7 .noteText,#mermaid-svg-KGtbiTrmQaZPeQC7 .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-KGtbiTrmQaZPeQC7 .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-KGtbiTrmQaZPeQC7 .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-KGtbiTrmQaZPeQC7 .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-KGtbiTrmQaZPeQC7 .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 .section{stroke:none;opacity:0.2}#mermaid-svg-KGtbiTrmQaZPeQC7 .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-KGtbiTrmQaZPeQC7 .section2{fill:#fff400}#mermaid-svg-KGtbiTrmQaZPeQC7 .section1,#mermaid-svg-KGtbiTrmQaZPeQC7 .section3{fill:#fff;opacity:0.2}#mermaid-svg-KGtbiTrmQaZPeQC7 .sectionTitle0{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .sectionTitle1{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .sectionTitle2{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .sectionTitle3{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-KGtbiTrmQaZPeQC7 .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 .grid path{stroke-width:0}#mermaid-svg-KGtbiTrmQaZPeQC7 .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-KGtbiTrmQaZPeQC7 .task{stroke-width:2}#mermaid-svg-KGtbiTrmQaZPeQC7 .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 .taskText:not([font-size]){font-size:11px}#mermaid-svg-KGtbiTrmQaZPeQC7 .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-KGtbiTrmQaZPeQC7 .task.clickable{cursor:pointer}#mermaid-svg-KGtbiTrmQaZPeQC7 .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-KGtbiTrmQaZPeQC7 .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-KGtbiTrmQaZPeQC7 .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-KGtbiTrmQaZPeQC7 .taskText0,#mermaid-svg-KGtbiTrmQaZPeQC7 .taskText1,#mermaid-svg-KGtbiTrmQaZPeQC7 .taskText2,#mermaid-svg-KGtbiTrmQaZPeQC7 .taskText3{fill:#fff}#mermaid-svg-KGtbiTrmQaZPeQC7 .task0,#mermaid-svg-KGtbiTrmQaZPeQC7 .task1,#mermaid-svg-KGtbiTrmQaZPeQC7 .task2,#mermaid-svg-KGtbiTrmQaZPeQC7 .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-KGtbiTrmQaZPeQC7 .taskTextOutside0,#mermaid-svg-KGtbiTrmQaZPeQC7 .taskTextOutside2{fill:#000}#mermaid-svg-KGtbiTrmQaZPeQC7 .taskTextOutside1,#mermaid-svg-KGtbiTrmQaZPeQC7 .taskTextOutside3{fill:#000}#mermaid-svg-KGtbiTrmQaZPeQC7 .active0,#mermaid-svg-KGtbiTrmQaZPeQC7 .active1,#mermaid-svg-KGtbiTrmQaZPeQC7 .active2,#mermaid-svg-KGtbiTrmQaZPeQC7 .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-KGtbiTrmQaZPeQC7 .activeText0,#mermaid-svg-KGtbiTrmQaZPeQC7 .activeText1,#mermaid-svg-KGtbiTrmQaZPeQC7 .activeText2,#mermaid-svg-KGtbiTrmQaZPeQC7 .activeText3{fill:#000 !important}#mermaid-svg-KGtbiTrmQaZPeQC7 .done0,#mermaid-svg-KGtbiTrmQaZPeQC7 .done1,#mermaid-svg-KGtbiTrmQaZPeQC7 .done2,#mermaid-svg-KGtbiTrmQaZPeQC7 .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-KGtbiTrmQaZPeQC7 .doneText0,#mermaid-svg-KGtbiTrmQaZPeQC7 .doneText1,#mermaid-svg-KGtbiTrmQaZPeQC7 .doneText2,#mermaid-svg-KGtbiTrmQaZPeQC7 .doneText3{fill:#000 !important}#mermaid-svg-KGtbiTrmQaZPeQC7 .crit0,#mermaid-svg-KGtbiTrmQaZPeQC7 .crit1,#mermaid-svg-KGtbiTrmQaZPeQC7 .crit2,#mermaid-svg-KGtbiTrmQaZPeQC7 .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-KGtbiTrmQaZPeQC7 .activeCrit0,#mermaid-svg-KGtbiTrmQaZPeQC7 .activeCrit1,#mermaid-svg-KGtbiTrmQaZPeQC7 .activeCrit2,#mermaid-svg-KGtbiTrmQaZPeQC7 .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-KGtbiTrmQaZPeQC7 .doneCrit0,#mermaid-svg-KGtbiTrmQaZPeQC7 .doneCrit1,#mermaid-svg-KGtbiTrmQaZPeQC7 .doneCrit2,#mermaid-svg-KGtbiTrmQaZPeQC7 .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-KGtbiTrmQaZPeQC7 .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-KGtbiTrmQaZPeQC7 .milestoneText{font-style:italic}#mermaid-svg-KGtbiTrmQaZPeQC7 .doneCritText0,#mermaid-svg-KGtbiTrmQaZPeQC7 .doneCritText1,#mermaid-svg-KGtbiTrmQaZPeQC7 .doneCritText2,#mermaid-svg-KGtbiTrmQaZPeQC7 .doneCritText3{fill:#000 !important}#mermaid-svg-KGtbiTrmQaZPeQC7 .activeCritText0,#mermaid-svg-KGtbiTrmQaZPeQC7 .activeCritText1,#mermaid-svg-KGtbiTrmQaZPeQC7 .activeCritText2,#mermaid-svg-KGtbiTrmQaZPeQC7 .activeCritText3{fill:#000 !important}#mermaid-svg-KGtbiTrmQaZPeQC7 .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-KGtbiTrmQaZPeQC7 g.classGroup text .title{font-weight:bolder}#mermaid-svg-KGtbiTrmQaZPeQC7 g.clickable{cursor:pointer}#mermaid-svg-KGtbiTrmQaZPeQC7 g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-KGtbiTrmQaZPeQC7 g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-KGtbiTrmQaZPeQC7 .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-KGtbiTrmQaZPeQC7 .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-KGtbiTrmQaZPeQC7 .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-KGtbiTrmQaZPeQC7 .dashed-line{stroke-dasharray:3}#mermaid-svg-KGtbiTrmQaZPeQC7 #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-KGtbiTrmQaZPeQC7 #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-KGtbiTrmQaZPeQC7 #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-KGtbiTrmQaZPeQC7 #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-KGtbiTrmQaZPeQC7 #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-KGtbiTrmQaZPeQC7 #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-KGtbiTrmQaZPeQC7 #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-KGtbiTrmQaZPeQC7 #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-KGtbiTrmQaZPeQC7 .commit-id,#mermaid-svg-KGtbiTrmQaZPeQC7 .commit-msg,#mermaid-svg-KGtbiTrmQaZPeQC7 .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-KGtbiTrmQaZPeQC7 g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-KGtbiTrmQaZPeQC7 g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-KGtbiTrmQaZPeQC7 g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-KGtbiTrmQaZPeQC7 .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-KGtbiTrmQaZPeQC7 .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-KGtbiTrmQaZPeQC7 .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-KGtbiTrmQaZPeQC7 .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-KGtbiTrmQaZPeQC7 .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-KGtbiTrmQaZPeQC7 .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-KGtbiTrmQaZPeQC7 .edgeLabel text{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-KGtbiTrmQaZPeQC7 .node circle.state-start{fill:black;stroke:black}#mermaid-svg-KGtbiTrmQaZPeQC7 .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-KGtbiTrmQaZPeQC7 #statediagram-barbEnd{fill:#9370db}#mermaid-svg-KGtbiTrmQaZPeQC7 .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-KGtbiTrmQaZPeQC7 .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-KGtbiTrmQaZPeQC7 .statediagram-state .divider{stroke:#9370db}#mermaid-svg-KGtbiTrmQaZPeQC7 .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-KGtbiTrmQaZPeQC7 .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-KGtbiTrmQaZPeQC7 .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-KGtbiTrmQaZPeQC7 .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-KGtbiTrmQaZPeQC7 .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-KGtbiTrmQaZPeQC7 .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-KGtbiTrmQaZPeQC7 .note-edge{stroke-dasharray:5}#mermaid-svg-KGtbiTrmQaZPeQC7 .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-KGtbiTrmQaZPeQC7 .error-icon{fill:#522}#mermaid-svg-KGtbiTrmQaZPeQC7 .error-text{fill:#522;stroke:#522}#mermaid-svg-KGtbiTrmQaZPeQC7 .edge-thickness-normal{stroke-width:2px}#mermaid-svg-KGtbiTrmQaZPeQC7 .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-KGtbiTrmQaZPeQC7 .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-KGtbiTrmQaZPeQC7 .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-KGtbiTrmQaZPeQC7 .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-KGtbiTrmQaZPeQC7 .marker{fill:#333}#mermaid-svg-KGtbiTrmQaZPeQC7 .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-KGtbiTrmQaZPeQC7 { color: rgba(0, 0, 0, 0.75); font: ; } 初始字符串L0 L_left L_right L_left L_right L_left L_right L_left L_right

python 字典 / map / 哈希表

因为分割是固定的。因此，只需要记录每一个字母的最左侧位置和最右侧的位置，即可完整保存分割所需要的信息。因此，第一次遍历整个字符串，保留所有字母的最左侧和最右侧的数据。若仅存在一个，则最右侧索引记为 -1.例如：

eaaaabaaec {‘e’: 0, ‘a’: 1, ‘b’: 2, ‘c’: 3} [0, 8], [1, 7], [5, -1], [9, -1]

第二次遍历，从第一个list [left, right]开始遍历，以minIndex和 maxIndex分别表示，左侧最小值和右侧最大值。当maxIndex 小于当前List的左侧节点时，即可进行一次划分当maxIndex 为-1 时即可进行一次划分，

最终的代码

def partitionLabels(S): """ :type S: str :rtype: List[int] """ charDict = {} indexList = [] for i,s in enumerate(S): if s in charDict.keys(): index = charDict[s] indexList[index][1] = i else: charDict[s] = len(indexList) indexList.append([i,-1]) result = [] minIndex = indexList[0][0] maxIndex = indexList[0][1] for index,i in enumerate(indexList): if index == 0: continue if maxIndex == -1: minIndex = i[0] maxIndex = i[1] result.append(1) elif maxIndex < i[0]: result.append(maxIndex - minIndex + 1) minIndex = i[0] maxIndex = i[1] else: maxIndex = max(maxIndex,i[1]) # print(("%s :: %s"%(minIndex,maxIndex))) if maxIndex == -1: result.append(1) else: result.append(maxIndex - minIndex + 1) # 用于调试 # return result,indexList,charDict return result

结果：

后续优化方向

保留尽可能少的信息；是否可以仅遍历一次即得出结果。使用提示信息进行结构上的优化

最新回复(0)