いいものをつくろう

CTOの日記

アルゴリズム

斜めにループできますか?プログラミング

更新日:

この問題はleetcode longest palindrome substringですが

かなり勉強させていただきました。

まず使い慣れたfor i in range(5)で行ごとに操作するのではなく

斜めに操作することを考えていきましょう。

なぜなら、この問題を解くのに斜めの操作が必要だったらからです

b = 5
S = [[0]*b for i in range(b)]
for i in range(b):
    for j in range(5):
        S[i][j] = b * i + j
for s in S:
    print(s)



print("loop horizontally")
for s in S:
    for o in s:
        print(o, end=",")


print("loop vertically")
for r in range(len(S)):
    for c in range(len(S)):
        print(S[c][r], end=",")


print("loop diagonally")
for i in range(len(S)):
    for r in range(len(S)):
        for c in range(r, len(S)):
            try:
                print(S[r][c+i], end=",")
            except:
                pass
            break

一番最後のが斜めです。

しかし、この解答を見たときに、もう少しシンプルにかけることがわかりました

https://leetcode.com/problems/longest-palindromic-substring/discuss/297375/Python-easy-to-understand-DP-solution

の最後の部分です

step = 2
        for _ in range(length-2):
            i = 0
            j = i+step
            while (i < length) and (j < length):
                arr_2d[i][j] = (s[i] == s[j]) and arr_2d[i+1][j-1]
                if arr_2d[i][j] and (j-i+1 > max_sub_len):
                    max_sub_len = j-i+1
                    substring = (i, j)
                i += 1
                j += 1
            step += 1

一つは行を操作するfor が外側にありますね

そして内側はwhileで階段状に操作しているところがあります、これでいいんですね。

ちょっとこれを元に自分のソースコードを改造してみます

print("loop diagonally wiht for and while")
for offset in range(len(S)):
    r = 0
    c = 0 + offset
    while r < len(S) and c < len(S):
        print(S[r][c], end=",")
        r+=1
        c+=1

 

とうことで現れ出たのがこのループです。3つ目のループが内分、少しスッキリしましたね。

ではこれで longest palindrome substringを再実装していきます。

 

以上です

 

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.