概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

基本的にeasyのacceptanceが高い順から解いていこうかと思います。

前回
ゼロから始めるLeetCode Day1 「1389. Create Target Array in the Given Order」

問題

1108. Defanging an IP Address

Input: address = "1.1.1.1" Output: "1[.]1[.]1[.]1"

Input: address = "255.100.50.0" Output: "255[.]100[.]50[.]0"

与えられたIPアドレスの.を[.]に代えるだけです。

class Solution:
    def defangIPaddr(self, address: str) -> str:
        address = address.replace('.','[.]')
        return address
# Runtime: 24 ms, faster than 88.37% of Python3 online submissions for Defanging an IP Address.
# Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for Defanging an IP Address.

replace()を使うだけで終わり！

・・・と思っていたのですが、そもそもaddressに代入せずに直接returnした方が速いのでは？と思い、書き直す。

class Solution:
    def defangIPaddr(self, address: str) -> str:
    return address.replace('.','[.]')
# Runtime: 24 ms, faster than 88.37% of Python3 online submissions for Defanging an IP Address.
# Memory Usage: 13.7 MB, less than 100.00% of Python3 online submissions for Defanging an IP Address.

メモリの使用量が少し減っただけでした。

Discussをチラッとみてみたら他にはこれがメジャーっぽい。
一旦split関数を使ってリストに代入し、join関数を使って数字の間に'[.]'を挿入するというもの。


class Solution:
    def defangIPaddr(self, address: str) -> str:
        return "[.]".join(address.split("."))
# Runtime: 28 ms, faster than 65.40% of Python3 online submissions for Defanging an IP Address.
# Memory Usage: 13.7 MB, less than 100.00% of Python3 online submissions for Defanging an IP Address.

ちなみにsplit関数とjoin関数はそれぞれ以下のような仕様です。

str.split(sep=None, maxsplit=-1)
文字列を sep をデリミタ文字列として区切った単語のリストを返します。maxsplit が与えられていれば、最大で maxsplit 回分割されます (つまり、リストは最大 maxsplit+1 要素になります)。 maxsplit が与えられないか -1 なら、分割の回数に制限はありません (可能なだけ分割されます)。
sep が与えられた場合、連続した区切り文字はまとめられず、空の文字列を区切っていると判断されます(例えば '1,,2'.split(',') は ['1', '', '2'] を返します)。引数 sep は複数の文字にもできます (例えば '1<>2<>3'.split('<>') は ['1', '2', '3'] を返します)。区切り文字を指定して空の文字列を分割すると、 [''] を返します。
例えば:

'1,2,3'.split(',')
['1', '2', '3']
'1,2,3'.split(',', maxsplit=1)
['1', '2,3']
'1,2,,3,'.split(',')
['1', '2', '', '3', '']

sep が指定されていないか None の場合、異なる分割アルゴリズムが適用されます。連続する空白文字はひとつのデリミタとみなされます。また、文字列の先頭や末尾に空白があっても、結果の最初や最後に空文字列は含まれません。よって、空文字列や空白だけの文字列を None デリミタで分割すると [] が返されます。
例えば:

'1 2 3'.split()
['1', '2', '3']
'1 2 3'.split(maxsplit=1)
['1', '2 3']
'   1   2   3   '.split()
['1', '2', '3']

str.join(iterable)
iterable 中の文字列を結合した文字列を返します。 iterable に bytes オブジェクトのような非文字列の値が存在するなら、 TypeError が送出されます。要素間のセパレータは、このメソッドを提供する文字列です。

細かい関数は使いながら覚えていくのがいいとは思いますが、この問題に関して言えばreplace関数を使った方がシンプルでわかりやすいと思いました。

ゼロから始めるLeetCode Day2 「1108. Defanging an IP Address」

概要

問題