概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。
その対策としてLeetCodeなるサイトで対策を行うようです。
※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。
未経験のエンジニアなので、基本的に簡単なもの（easyでacceptanceが高い順）から解いていきます。
問題
2124. Check if All A's Appears Before All B's
文字「a」と「b」だけで構成される文字列「s」が与えられたとき、文字列中のすべての「a」がすべての「b」の前に現れる場合に真を返す。そうでない場合は偽を返す。
例1:
入力: s = "aaabbb"
出力: true
説明：
aは添字0、1、2にあり、bは添字3、4、5にある。
したがって、すべての『a』はすべての『b』の前に現れるので、真を返す。
例2:
入力: s = "abab"
出力: false
説明
添字2に『a』があり、添字1に『b』がある。
したがって、すべての『a』がすべての『b』の前に現れるわけではないので、偽を返す。
例3:
入力: s = "bbb"
出力: true
説明
a『はないので、すべての』a『はすべての』b'の前に現れ、真を返す。
制約条件:
・1 <= matches.length <= 105
・matches[i].length == 2
・1 <= winneri, loseri <= 105
・winneri != loseri
・All matches[i] are unique.
解法
class Solution:
def checkString(self, s: str) -> bool:
b_found = False
for char in s:
if char == 'b':
b_found = True
elif char == 'a' and b_found:
return False
return True
b_found = False
「b」という文字が見つかったかどうかを追跡するために使われる。
最初はまだ「b」 は見つかっていないので、Falseに設定されている。
elif char == 'a' and b_found
「もし現在の文字が 「a」 であり、かつ、すでにどこかで 「b」 が見つかっているならば」という状況をチェックしている。
これは、'b' の後に 'a' が出現したことを意味する。
真の場合、関数の戻り値としてFalseが返却される。
例
- 入力: s = "abab"
| インデックス | char と b_found の状態 | 説明 |
|---|---|---|
| 0 | char が 「a」、b_found は False | まだ「b」 は見つかっていないので、b_found は False のまま。 |
| 1 | char が 「b」、b_found は True | b_found が True に設定される。 |
| 2 | char が 「a」、b_found は False | このとき、b_found はすでに True になっています。これは、「b」 の後に 「a」 が現れたので、char == 「a」 and b_foundを満たし、関数は False を返す。 |
別解
正規表現を用いた別解
import re
class Solution:
def checkString(self, s: str) -> bool:
if re.search("ba", s):
return False
else:
return True
re.search("ba", s):
re.search()関数は、文字列sの中にパターン「ba」が見つかるかどうかを検索する。
第一引数の「"ba"」は検索する正規表現パターンであり、文字「b」の直後に文字「a」が続くシーケンスを意味する。
第二引数の「s」は検索対象の文字列。
もしパターンが見つかれば、マッチオブジェクトが返され、真と評価される。
もしパターンが見つからなければ、Noneが返され、偽と評価される。
Discussion