算法總結 - 字元串 - 字元壓縮與延伸

• 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字元串的時候注意起始位置