义乌城市投资建设集团网站,人力资源公司劳务派遣,类型: 营销型网站建设,广告网站建设最专业字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段#xff0c;同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。 示例 1#xff1a;输入#xff1a;S ababcbacadefegdehijhklij
输出#xff1a;[9,7,8]
解释同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。 示例 1输入S ababcbacadefegdehijhklij
输出[9,7,8]
解释
划分结果为 ababcbaca, defegde, hijhklij。
每个字母最多出现在一个片段中。
像 ababcbacadefegde, hijhklij 的划分是错误的因为划分的片段数较少。 提示
S的长度在[1, 500]之间。 S只包含小写字母 a 到 z 。 思路看到题目先想到了把S拆成两段(如果S可划分)之后把拆开的S分段再进行拆分(如果可拆分),如果不可拆分就把当前分段
的长度写入结果链表
1.怎么判断是不是可拆分
先保存当前字符串各字符数量用map,数组都可以之后复制一下先前统计的结果然后从头开始遍历执行--操作。如果当前字符的数量为0那就说明该字符只出现在当前字符与当前字符前面这个字符是可以拆分的开始看他前面的字符是不是都可以拆分如果他前面的字符当前的数量不为0说明后面还有继续向下遍历。如果当前字符前面的字符的也都不出现在后面说明该字段可以拆分。
2.实现
可拆分继续拆
不可拆分当前字符长度保存进结果链表
代码
class Solution {ListInteger result new ArrayList();void chaifen(String s){if(s.length()0){return ;}int arr[] new int[26];//统计各字符出现的次数for(int i0;is.length();i){arr[s.charAt(i)-a]1;}int brr[] arr;int index 0;for(int i0;is.length();i){brr[s.charAt(i)-a]-1;int j0;//当前字符的数量为0说明不会出现在后面了if(brr[s.charAt(i)-a]0){//检索前面的字符是不是也都不会出现在后面for(j0;ji;j){if(brr[s.charAt(j)-a]!0){break;}}}//index记录可以拆分的位置如果不可拆分位置就是字符串尾部if(ji){index i;break;}}if(index!s.length()-1){chaifen(s.substring(0,index1));chaifen(s.substring(index1,s.length()));}else{result.add(s.length());}}public ListInteger partitionLabels(String S) {chaifen(S);return result;}
}
