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