C++刷leetcode（1147. 段式回文）【双指针】【贪心思想】

糖逗

题目描述：

1. 
   
2. 段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符 而不是 单个字母。
   
3. 
   
4. 举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把 "volvo" 分为 "vo"、"l"、"vo" 三段，则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。
   
5. 
   
6. 
   
7. 
   
8. 给你一个字符串 text，在确保它满足段式回文的前提下，请你返回 段 的 最大数量 k。
   
9. 
   
10. 如果段的最大数量为 k，那么存在满足以下条件的 a_1, a_2, ..., a_k：
    
11. 
    
12. 每个 a_i 都是一个非空字符串；
    
13. 将这些字符串首位相连的结果 a_1 + a_2 + ... + a_k 和原始字符串 text 相同；
    
14. 对于所有1 <= i <= k，都有 a_i = a_{k+1 - i}。
    
15. 
    
16. 
    
17. 示例 1：
    
18. 
    
19. 输入：text = "ghiabcdefhelloadamhelloabcdefghi"
    
20. 输出：7
    
21. 解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。
    
22. 示例 2：
    
23. 
    
24. 输入：text = "merchant"
    
25. 输出：1
    
26. 解释：我们可以把字符串拆分成 "(merchant)"。
    
27. 示例 3：
    
28. 
    
29. 输入：text = "antaprezatepzapreanta"
    
30. 输出：11
    
31. 解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。
    
32. 示例 4：
    
33. 
    
34. 输入：text = "aaa"
    
35. 输出：3
    
36. 解释：我们可以把字符串拆分成 "(a)(a)(a)"。
    
37. 
    
38. 
    
39. 提示：
    
40. 
    
41. text 仅由小写英文字符组成。
    
42. 1 <= text.length <= 1000

复制代码

1. class Solution {
   
2. public:
   
3.     int longestDecomposition(string text) {
   
4.         int res = 0;
   
5.         int len = text.size();
   
6.         if(len <= 0) return len;
   
7.         int left = -1, right = len-1;
   
8.         while(left != right){
   
9.             char temp1 = text[right];
   
10.             int length = 0;
    
11.             int i;
    
12.             for(i = left + 1; i <= right; i++){
    
13.                 length++;
    
14.                 if(text[i] == temp1 && text.substr(left+1, length) == text.substr(right - length+1, length)){
    
15.                     res += 2;
    
16.                     left = i;
    
17.                     break;
    
18.                 }
    
19.             }
    
20.             if(left == right){
    
21.                 res--;
    
22.                 break;
    
23.             }
    
24.             right -= length;
    
25.         }
    
26.         return res;
    
27.     }
    
28. };

复制代码

糖逗

糖逗

欢迎订阅一起刷题