結果
問題 |
No.52 よくある文字列の問題
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:54:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 41 ms / 5,000 ms |
コード長 | 920 bytes |
コンパイル時間 | 197 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 52,608 KB |
最終ジャッジ日時 | 2025-03-20 18:56:12 |
合計ジャッジ時間 | 1,369 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 |
ソースコード
S = input().strip() n = len(S) # Initialize DP table where dp[l][r] is a set of possible strings dp = [[set() for _ in range(n)] for _ in range(n)] # Base case: single character substrings for i in range(n): dp[i][i].add(S[i]) # Fill DP table for substrings of length 2 to n for length in range(2, n + 1): for l in range(n - length + 1): r = l + length - 1 # Take left character and append all possible strings from substring (l+1, r) left_set = dp[l + 1][r] temp_left = {S[l] + s for s in left_set} if left_set else set() # Take right character and append all possible strings from substring (l, r-1) right_set = dp[l][r - 1] temp_right = {S[r] + s for s in right_set} if right_set else set() # Combine both possibilities dp[l][r] = temp_left.union(temp_right) # The answer is the size of the set at dp[0][n-1] print(len(dp[0][n - 1]))