Return the largest possible k
such that there exists a_1, a_2, ..., a_k
such that:
- Each
a_i
is a non-empty string; - Their concatenation
a_1 + a_2 + ... + a_k
is equal totext
; - For all
1 <= i <= k
,a_i = a_{k+1 - i}
.
Example 1:
Input: text = "ghiabcdefhelloadamhelloabcdefghi" Output: 7 Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".
Example 2:
Input: text = "merchant" Output: 1 Explanation: We can split the string on "(merchant)".
Example 3:
Input: text = "antaprezatepzapreanta" Output: 11 Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".
Example 4:
Input: text = "aaa" Output: 3 Explanation: We can split the string on "(a)(a)(a)".
Solution: Greedy
Break the string when the shortest palindrome is found.
prefer to use string_view
Time complexity: O(n^2)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua, 0 ms, 8.7 ms class Solution { public: int longestDecomposition(string_view text) { const int n = text.length(); if (n == 0) return 0; for (int l = 1; l <= n / 2; ++l) { if (text.substr(0, l) == text.substr(n - l)) return 2 + longestDecomposition(text.substr(l, n - 2 * l)); } return 1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment