NeetCode 150 [Arrays & Hashing]:medium 3/6

NeetCodeのSolutionを書いていく

Encode and Decode Strings

問題概要

文字列のリストを単一の文字列にエンコードしましょう。
エンコードされた文字列は元の文字列のリストにデコードして戻すことができます。
encodeとdecodeを実装しましょう。

配列数は0以上100未満。
文字列長は0以上200未満。

計算時間はO(m)、メモリーはO(1)を目指す。
mは全ての文字の合算数。

例

Input: ["neet","code","love","you"]
Output:["neet","code","love","you"]

Input: ["we","say",":","yes"]
Output: ["we","say",":","yes"]

メモ

シリアライズ、デシリアライズすればいい。
jsonを使えば一発。
でもそういう問題ではないのかな？

自分で実装しようと思うとどうなるんだろうか。
問題は文字列リテラルのデリミタのエスケープ？
いや、違うか、それは文字列として扱っている時点で解決されているから、シリアライズする時の区切り文字か。

文字列数,:字列文字列数:文字列
みたいに最初に「文字列数:」の情報を入れた形の文字列にすれば復元できそう。
でもこれだと、メモリがO(1)ではなくO(m)になる。
シリアライズする時点でメモリO(1)は無理な気がするけど。。。

答えを見てもO(1)には見えない。
chatGptにきいてもO(n)とのこと。
うぅむ。

from typing import List

# import json
# class Solution:
#     def encode(self, strs: List[str]) -> str:
#         return json.dumps(strs)

#     def decode(self, s: str) -> List[str]:
#         return json.loads(s)


class Solution:
    def encode(self, strs: List[str]) -> str:
        ret = ""
        for s in strs:
            ret += str(len(s)) + ":"
            ret += s
        return ret

    def decode(self, s: str) -> List[str]:
        ret = []
        temp = ""
        i = 0
        while i < len(s):
            c = s[i]
            i += 1
            temp += c if c != ":" else ""
            if c == ":":
                strlen = int(temp)
                end = i + strlen
                ret.append(s[i:end])
                i = end
                temp = ""
        return ret