[每日一题]最少划分子串

数据结构和算法►字符串 , , , , 评论

来源:

lintcode-最少划分子串

描述

给定一个包含n个小写字母的字符串s，要求将字符串划分成若干个连续子串，子串中的字母类型相同，同时子串的字母个数不超过k，输出最少划分的子串数量。

样例

  1. 给定 s = “aabbbc”, k = 2, 返回4
1
2
解释：
划分成 "aa", "bb", "b", "c" 四个子串
  1. 给定 s = “aabbbc”, k = 3, 返回3
1
2
解释：
划分成 "aa", "bbb", "c" 三个子串

解决思路

这道题比较简单,就是在遍历的过程中,当发现不符合

  1. 当前字符与上一个字符相同
  2. 当前子串长度小于k

任意一种情况时,子串个数加一即可.

看到这个当前字符与上一个字符不同,我就想到了栈,因此使用栈来实现.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
   * 最少划分子串
   */
  public static int getAns(String s, int k) {
    // Write your code here
    //空栈
    Stack<Character> tmp = new Stack<>();
    //结果
    int result = 0;

    for (int i = 0; i < s.length(); ) {
      //拿到当前字符
      Character current = s.charAt(i);

      //如果栈不为空
      if (tmp.size() > 0) {
        //如果栈里的字符数量大于k,或者当前字符与栈顶元素不同,清空栈,结果+1,然后跳过后续代码继续循环
        if (tmp.size() >= k || !tmp.peek().equals(current)) {
          tmp.clear();
          result++;
          continue;
        }
      }
      //如果栈为空,和不满足上述两个条件的,将当前元素入栈,继续向后遍历下一个字符
      tmp.push(current);
      i++;
    }
    //由于最后一个子串跳出循环时,没有进行result+1操作,这里补上.
    return result + 1;
  }

话不多说,都在注释里了.

完。




ChangeLog

2018-11-27 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。