import time
def timeit(func):
def wrapped(*args, **kwargs):
start = time.time()
ret = func(*args, **kwargs)
elapsed = time.time() - start
print("elapsed: %s" % elapsed)
return ret
return wrapped
class Solution:
@timeit
def longestPalindrome(self, S: str) -> str:
length = len(S)
dp = [[0]*length for _ in range(length)]
result = ""
for offset in range(length):
r = 0
c = 0 + offset
while r < length and c < length:
if (r+1 < length and c-1 >= 0 and dp[r+1][c-1] == 1) or (c-1 < r+1):
if S[r] == S[c]: # This is palindrome
dp[r][c] = 1
if c+1 - r > len(result):
result = S[r:c+1]
r+=1
c+=1
return result
みなさま、目標に近づいてますでしょうか？
おはようございます。
実行時間役O(n**3)の解
#-*- coding: utf-8 -*-
from typing import List
import math
class Solution:
def is_parandrome(self, s):
half_idx = math.ceil(len(s)/2)
j = len(s)-1
i = 0
while i <= j:
if s[i] != s[j]: return False
i += 1
j -= 1
#print("is_parandrome(%s) == yes" % s)
return True
def longestPalindrome(self, s: str) -> str:
if len(s) <= 1: return s
ret = s[0]
for i in range(len(s)):
for j in range(i+1, len(s)):
#print (i, j)
y = self.is_parandrome(s[i:j+1])
ret = s[i:j+1] if y and len(s[i:j+1]) > len(ret) else ret
return ret
アルゴリズムとしては正解なのですが
実行時間オーバーなので最後の90/100ケース目あたりでパスしません。
どこを削ることができるでしょうか？( backtracking的枝刈りが有効か？）
それても全然違う考え方が必要でしょうか？(DPは有効か？)
経験からですが、substring問題とくればdpと考えてもいいでしょう
ではどうやってdpを組み立てればいいのでしょうか？
これは難しいですね。
とりあえず、string * stringのテーブル書いてみるのがいいんじゃないでしょうか。
そっからまたパターンを探していくのです。個人的にはとりあえず不正解でもいいのでたたき台を書き出して、
そこから正解の落とし込んでいくのが性に合っているようです。
とは行っても難しいでうよねー、毎回dp問題。よくそんなこと思いつくなーって解答を見ていつも思います
めげずに頑張りましょー
ちょっと説明が難しですが、内側がpalindromeだったら外側だけ常にチェックしていけばいい
という戦法です。
#-*- coding: utf-8 -*-
from typing import List
import math
class Solution:
def longestPalindrome(self, s: str) -> str:
#logging.basicConfig(level=logging.INFO, format="%(message)s")
dp = [[-1]*len(s) for i in range(len(s))]
# logging.debug("=== dp ===")
# for row in dp:
# logging.debug(row)
# logging.debug("=== main ===")
for i in range(len(s)):
for r in range(len(s)):
for c in range(r, len(s)):
try:
x = dp[r][c+i]
if i == 0: dp[r][c+i] = 1
else: dp[r][c+i] = 0
except:
pass
break
# logging.debug("=== dp ===")
# for row in dp:
# logging.debug(row)
if len(s) == 0: return s
lp = s[0]
# loop diagonally
for i in range(len(s)):
for r in range(len(s)):
for c in range(r, len(s)):
try:
x = dp[r][c+i]
#logging.debug("(r, c+i) = (%d, %d)" % (r, c+i))
# 1-left-lower
try:
mid = dp[r+1][c+i-1]
except:
mid = 0
if s[r] == s[c+i] and (mid == 1 or mid == -1):
#logging.debug("--- hit ---")
dp[r][c+i] = 1
# update max
if c+i+1 - r > len(lp):
lp = s[r:c+i+1]
#logging.debug("mid[%s][%s](letters in the middle) is palandrome:%s" % (r+1, c+i-1, mid))
except:
pass
break
# logging.debug("=== dp ===")
# for row in dp:
# logging.debug(row)
return lp
import logging
logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.basicConfig(level=logging.DEBUG, format="%(message)s")
s = "babad"
s = "cbbd"
# time-exceeded
s = "kyyrjtdplseovzwjkykrjwhxquwxsfsorjiumvxjhjmgeueafubtonhlerrgsgohfosqssmizcuqryqomsipovhhodpfyudtusjhonlqabhxfahfcjqxyckycstcqwxvicwkjeuboerkmjshfgiglceycmycadpnvoeaurqatesivajoqdilynbcihnidbizwkuaoegmytopzdmvvoewvhebqzskseeubnretjgnmyjwwgcooytfojeuzcuyhsznbcaiqpwcyusyyywqmmvqzvvceylnuwcbxybhqpvjumzomnabrjgcfaabqmiotlfojnyuolostmtacbwmwlqdfkbfikusuqtupdwdrjwqmuudbcvtpieiwteqbeyfyqejglmxofdjksqmzeugwvuniaxdrunyunnqpbnfbgqemvamaxuhjbyzqmhalrprhnindrkbopwbwsjeqrmyqipnqvjqzpjalqyfvaavyhytetllzupxjwozdfpmjhjlrnitnjgapzrakcqahaqetwllaaiadalmxgvpawqpgecojxfvcgxsbrldktufdrogkogbltcezflyctklpqrjymqzyzmtlssnavzcquytcskcnjzzrytsvawkavzboncxlhqfiofuohehaygxidxsofhmhzygklliovnwqbwwiiyarxtoihvjkdrzqsnmhdtdlpckuayhtfyirnhkrhbrwkdymjrjklonyggqnxhfvtkqxoicakzsxmgczpwhpkzcntkcwhkdkxvfnjbvjjoumczjyvdgkfukfuldolqnauvoyhoheoqvpwoisniv"
ans = Solution().longestPalindrome(s)
logging.info(ans)
よっしゃこれでいけるだろうと思ったのですが、
多分最初の初期化の処理が結局O(n**3)になっちゃっているので
処理時間超過しているのではなんて思ったのですが、最後のループはbreakで常に終了するのでO(n**2)だと
思っています。
ちょっとここで他の人たちの解答を見ることにしました。
あまり悩んで一つの問題に時間をかけるよりは一定時間悩んだら次に行くようにします。
斜めにループできますか？プログラミング で書いた通り斜めの操作とい技を
覚えました。これを元に、
ではこれで longest palindrome substringを再実装していきます。
import logging
class Solution:
def longestPalindrome(self, S: str) -> str:
logging.basicConfig(level=logging.INFO, format="%(message)s")
logging.debug("palandrome(%s)" % S)
dp = [[0]*len(S) for _ in range(len(S))]
for i in range(len(S)):
dp[i][i] = 1
result = ""
for offset in range(len(S)):
r = 0
c = 0 + offset
while r < len(S) and c < len(S):
#logging.debug(dp[r][c], end=",")
if (r+1 < len(S) and c-1 >= 0 and dp[r+1][c-1] == 1) or (c-1 < r+1):
if S[r] == S[c]:
logging.debug("oh yes, this is palandrome")
if c+1 - r > len(result):
result = S[r:c+1]
dp[r][c] = 1
r+=1
c+=1
return result
とコーディングして、いざ提出してみると
１０００文字ちょうどのサンプルで弾かれてしまいました
ということで、
timeitで時間を測って削られるだけ削りました
0.4秒から0.27秒まで落とせたので、自信を持って提出、ドリャ!
import time
def timeit(func):
def wrapped(*args, **kwargs):
start = time.time()
ret = func(*args, **kwargs)
elapsed = time.time() - start
print("elapsed: %s" % elapsed)
return ret
return wrapped
class Solution:
@timeit
def longestPalindrome(self, S: str) -> str:
length = len(S)
dp = [[0]*length for _ in range(length)]
result = ""
for offset in range(length):
r = 0
c = 0 + offset
while r < length and c < length:
if (r+1 < length and c-1 >= 0 and dp[r+1][c-1] == 1) or (c-1 < r+1):
if S[r] == S[c]: # This is palindrome
dp[r][c] = 1
if c+1 - r > len(result):
result = S[r:c+1]
r+=1
c+=1
return result
やっと通りました。
もちろんtimeitの部分はコメントアウトして提出しました
驚いたのは、len(S)の部分が多用されていたのですが、これは事項時間に影響しないと
考えていたのですが、実はloopでO(n**2)でlen(S)が実行されるのは効いていたようです。
これからは細かい点ですが、len(S)は実行時間を食う対象として考えます。
で、パフォーマンスなのですが、以下の通り最低ラインなので
ここはもう一踏ん張りして、最適な解を取りに行きたいと思います。
ということで、一応自分の頭で
よぎった、外側に拡張していアイデアをちゃんと書けている人が沢山いるので
彼らか学び、次回は自分でもかけるようになるべく
練習して言いたいと思います。
逆に言えば自分の弱みは、アイデアを思いつてもそれをスラスラとコードに書き落とすことができないという
コーディング・実装力のなさです。これは練習で補っていきたいと思います
参考にするソースはこちらですね
一個一個愚直に拡張していくパターンです。
最初に思いついた時は具体的な速度O(what)になるのか？
ぼんやりでストップするのではなく、O(what)になるイメージをちゃんと掴めるところまで
実装をイメージできるかは非常に大切で、ここまでイメージが湧かないと面接などの限られた時間で能力を示すには意味がないと思います。
今回であればO(n)でなめてO(n)で拡張する(expand)するイメージをもつことでO(n**2)で計算できる
"""
dp使わずに拡大していく方法
"""
class Solution:
def expand_palindrome(self, S, i):
l = i - 1
r = i + 1
result = S[i]
while l >= 0 and r < len(S) and S[l] == S[r]: # check l and r within valid range
# this is palindrome
if r+1-l > len(result):
result = S[l:r+1]
l -= 1
r += 1
return result
def expand_palindrome_2(self, S, i, j):
l = i - 1
r = j + 1
if i < 0 or j >= len(S): return ""
if S[i] != S[j]: return ""
result = S[i:j+1]
while l >= 0 and r < len(S) and S[l] == S[r]: # check l and r within valid range
# this is palindrome
if r+1-l > len(result):
result = S[l:r+1]
l -= 1
r += 1
return result
@timeit
def longestPalindrome(self, S: str) -> str:
if len(S) <= 1: return S
result = S[0]
# palindrome starting with 1 char
for i, c in enumerate(S):
tmp = self.expand_palindrome(S, i)
if len(tmp) > len(result):
result = tmp
# palindrome starting with 1 char
for i, c in enumerate(S):
tmp = self.expand_palindrome_2(S, i, i+1)
if len(tmp) > len(result):
result = tmp
return result
上記の実装ももう少し削れるとは思いますが
ご覧のように、前よりはよくなりました。
このlongest palindrome substringという問題は
かなりてこづりました。しかしながら全部自分で実装することろまで持って行ったことで
１。longest最長とか聞かれたら、DPを連想し、とりあえずDP表を作る、という持っていき方
２。斜めの操作
３。今回であればO(n)でなめてO(n)で拡張する(expand)するイメージをもつことでO(n**2)で計算できる
とうい３つの学びを習得できました
以上です