算法总结 - 字符串 - 字符压缩与延伸

• 809. Expressive Words
• 604. Design Compressed String Iterator

809. Expressive Words

Sometimes people repeat letters to represent extra feeling, such as “hello” -> “heeellooo”, “hi” -> “hiiii”. In these strings like “heeellooo”, we have groups of adjacent letters that are all the same: “h”, “eee”, “ll”, “ooo”.

For some given string S, a query word is stretchy if it can be made to be equal to S by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is 3 or more.

For example, starting with “hello”, we could do an extension on the group “o” to get “hellooo”, but we cannot get “helloo” since the group “oo” has size less than 3. Also, we could do another extension like “ll” -> “lllll” to get “helllllooo”. If S = “helllllooo”, then the query word “hello” would be stretchy because of these two extension operations: query = “hello” -> “hellooo” -> “helllllooo” = S.

Given a list of query words, return the number of words that are stretchy.

Example:

Input:

S = “heeellooo”

words = [“hello”, “hi”, “helo”]

Output: 1

Explanation:

We can extend “e” and “o” in the word “hello” to get “heeellooo”.

We can’t extend “helo” to get “heeellooo” because the group “ll” is not size 3 or more.

Abstract

• 给出了一个字符串，其中有些字母是为了表现“情绪”而重复出现了多次
• 给出了一个字符串数组，求有多少个字符串可以产生这样的情绪化词
• 表现语气最少需要一个字母重复三次。

Idea

• 简化情绪化次或者延伸候选字符串

Question to ask

• 怎么化简一个情绪词？

Solution

• 把情绪词和候选字符串每个字符依次对比， 一下情况不能构造情绪词
  • 字符相同， 情绪词重复字符的次数小于3且不等于候选字符串重复次数
  • 字符相同，情绪词重复字符次数小于候选字符串次数
  • 字符不同

Code

public int expressiveWords(String S, String[] words) {
  int cnt = 0;
  
  for (String s: words){
  		// m1
      if (helper(S, s)) cnt++;
  }
  return cnt;
}

private boolean helper(String s, String t){
  int i = 0;
  int j = 0;
  
  while(i < s.length() && j < t.length()){
      char cs = s.charAt(i);
      char ct = t.charAt(j);
      int ls = getLen(s, i);
      int lt = getLen(t, j);
      
      if (cs == ct){
          if ((ls < 3 && ls != lt) || lt > ls){
              return false;
          }
      }else{
          return false;
      }
      i = i + ls;
      j = j + lt;
  }
  
  // m2
  return i == s.length() && j == t.length();
}

private int getLen(String s, int i){
  int j = i;
  while(j < s.length() && s.charAt(j) == s.charAt(i)){
      j++;
  }
  return j - i;
}
           

Time Complexity

O(nl): n 候选词个数， l 最长候选词的长度

Space Complexity

O(1)

Mistake

1. 单纯把所有的重复字符简化成一个字符不能通过一下的测试用例
   • "zzzzzyyyyy"和[“zzyy”,“zy”,“zyy”]
   • "heeellooo"和 [“hello”, “hi”, “helo”]
2. 简化时要确保检查在情绪词和候选词中的每个字符，别忘记最后的字符

Summary

• 分情况考虑问题

604. Design Compressed String Iterator

题目链接

Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext.

The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.

next() - if the original string still has uncompressed characters, return the next letter; Otherwise return a white space.

hasNext() - Judge whether there is any letter needs to be uncompressed.

Note:

Please remember to RESET your class variables declared in StringIterator, as static/class variables are persisted across multiple test cases. Please see here for more details.

Example:

StringIterator iterator = new StringIterator(“L1e2t1C1o1d1e1”);

iterator.next(); // return ‘L’

iterator.next(); // return ‘e’

iterator.next(); // return ‘e’

iterator.next(); // return ‘t’

iterator.next(); // return ‘C’

iterator.next(); // return ‘o’

iterator.next(); // return ‘d’

iterator.hasNext(); // return true

iterator.next(); // return ‘e’

iterator.hasNext(); // return false

iterator.next(); // return ’ ’

Abstract

• 设计和实现压缩字符串的迭代器，支持函数：next和hasNext。
• 压缩字符串以字母+出现次数的格式给出(“L1e2t1C1o1d1e1”)

Idea

• 选择数据结构可以存储字母和出现的次数

Question to ask

使用Queue还是Stack，怎么处理next的情况？

Solution

• 定义一个Pair class存储字符以及出现的次数
• 用Queue存储所以的字符对
• 迭代的时候更新字符对中的出现次数

Code

class StringIterator {
    class Pair{
        char c;
        int cnt;
        public Pair(char c, int cnt){
            this.c = c;
            this.cnt = cnt;
        }
    }
    
    Deque<Pair> que = new ArrayDeque<>();
    public StringIterator(String cs) {
        int i = 0;
        int j = 0;
        while(i < cs.length()){
        	// m1
            j = i + 1;
            while(j < cs.length() && Character.isDigit(cs.charAt(j))){
                j++;
            }
            int cnt = Integer.parseInt(cs.substring(i + 1, j));
            que.offer(new Pair(cs.charAt(i), cnt));
            i = j;
        }
    }
    
    public char next() {
        char ans = ' ';
        if (!que.isEmpty()){
            Pair p = que.removeFirst();
            ans = p.c;
            if (p.cnt == 1){
                return ans;
            }else{
                que.addFirst(new Pair(p.c, p.cnt - 1));
            }
        }
        //m2
        return ans;
    }
    
    public boolean hasNext() {
        return !que.isEmpty();
    }
}
           

Time Complexity

O(n)

Space Complexity

O(n)

Mistake

1.注意字符次数的起始位置，j = i + 1

2.注意最终要返回一个字符

Summary

• parse字符串的时候注意起始位置