📚

LeetCode 443. String Compression - read/writeの2つのインデックスを扱う

2025/08/19に公開

LeetCode

tech

443. String Compression

Intuition

文字列の圧縮処理
- ループ処理で文字列をカウントすればよいか
- 仕様上、入力配列を変更したうえで、配列の長さを返す必要がある
  - 内部ループで書き込み用のindexを利用する
    - ["a","2","b","2","c","3","c"]最後のケア(c)などがうまくいかない。
    - 「配列の長さを返す必要がある」配列の長さを返すことで、呼び出し元で新しい配列と扱ってくれる模様。

python

for i in range(len(chars))でループしているため、write_indexが圧縮前のindexまでカウンティングされてしまうため下記コードはNG

# 間違ったコード
class Solution:
    def compress(self, chars: List[str]) -> int:
        count = 0
        writeIndex = 0

        for i in range(len(chars)):
            # グルーピングした値に対して2重ループでカウンティングして、途切れたら途中終了
            while i + count < len(chars) and chars[i + count] == chars[i]:
                count += 1

            chars[writeIndex] = chars[i]
            writeIndex += 1

            if count > 1:
                chars[writeIndex] = str(count)
                count = 0

        return writeIndex

write_indexとread_indexの2つを用意してwhileループを利用する
- forループより柔軟にindex処理が可能

class Solution:
    def compress(self, chars: List[str]) -> int:
        read_index = 0
        write_index = 0

        while read_index < len(chars):
            count = 0
            currentChar = chars[read_index] # read_indexを増やすためここで保持する
            # グルーピングした値に対して2重ループでカウンティングして、途切れたら途中終了
            while (read_index < len(chars) and chars[read_index] == currentChar):
                read_index += 1
                count += 1
            
            chars[write_index] = currentChar
            write_index += 1

            if count >1:
                for digit in str(count):
                    chars[write_index] = digit
                    write_index += 1

        return write_index # 書き込み後のindexを返すことを期待

文字列に対してforループ適用が可能

>>> for digit in str(12):
...     print(digit)
...
1
2

write_indexの引数について
- in-placeではなく新しいarr変数の作成のため関数から抜けるときにメモリ開放される
  - arr = arr[:2]という代入文は、arrという変数が指している先を変更するだけで、元のリスト自体の中身を変更しているわけない

>>> arr = [1,2,3]
>>> arr[:2]
[1, 2]
>>> arr = arr[:2]

Approach

他の言語でのアプローチを検討する。

ruby

chunkすることができるが、rubyならではの解法。

# @param {Character[]} chars
# @return {Integer}
def compress(chars)
  write_index = 0
  
  chars.chunk(&:itself).each do |key, group|
    chars[write_index] = key
    write_index += 1
    
    count = group.length
    if count > 1
      count.to_s.each_char do |digit|
        chars[write_index] = digit
        write_index += 1
      end
    end
  end
  
  return write_index
end

golang

var currentCharはstringではなくbyteで定義する。
- 一方、typescriptではstringで扱う

データ型	不変性	データの種類	主な使い道
string	不変	テキスト	テキストの表示や辞書のキーなど、変更しないデータの管理
[]byte	可変	バイナリデータ	データのバイト単位での操作、インプレースな変更
[]string	可変	文字列のリスト	複数の文字列のリスト管理

func compress(chars []byte) int {
	var read_index int = 0
	var write_index int = 0

	for read_index < len(chars) {
		var count int = 0
		var currentChar byte = chars[read_index]

		for read_index < len(chars) && currentChar == chars[read_index] {
			count++
			read_index++
		}

		chars[write_index] = currentChar
		write_index++

		if count > 1 {
			countStr := strconv.Itoa(count)
			for i := 0; i < len(countStr); i++ {
				chars[write_index] = countStr[i]
				write_index++
			}
		}
	}
	return write_index
}

typescript

count.toStringは関数の参照、count.toStringは関数呼び出し

function compress(chars: string[]): number {
    let write_index: number = 0
    let read_index: number = 0

    while(read_index < chars.length){
        let count: number = 0
        let currentChar: string = chars[read_index]
        while(read_index < chars.length && currentChar == chars[read_index]){
            count++
            read_index++
        }

        chars[write_index] = currentChar
        write_index++

        if (count > 1) {
            for(const digit of count.toString() ){
                chars[write_index] = digit
                write_index++
            }
        }
    }
    return write_index

};

学習のポイント

stringを文字列シーケンスとして扱ってforループの処理ができる。
read_indexとwrite_indexの2つのindexを扱いインクリメントのタイミングが異なる場合は、whileループが簡単
関数への引数は参照渡しされている

443. String Compression

Intuition

python

Approach

ruby

golang

typescript

学習のポイント

Discussion