迈塔 昂塞

tyw 发表于 2024-10-29 00:05
顺便问一下，panlindrom那道的followup是什么？感谢楼主！已加米

ChatGPT

1. import java.util.HashMap;
   
2. import java.util.Map;
   
3. 
   
4. public class Solution {
   
5.     private Map<String, Boolean> memo = new HashMap<>();
   
6. 
   
7.     public boolean validPalindrome(String s, int k) {
   
8.         return isValid(s, 0, s.length() - 1, k);
   
9.     }
   
10. 
    
11.     private boolean isValid(String s, int left, int right, int k) {
    
12.         // Base case: If k goes below 0, we can't delete more characters
    
13.         if (k < 0) return false;
    
14. 
    
15.         // Base case: If pointers cross, it's a palindrome or empty
    
16.         if (left >= right) return true;
    
17. 
    
18.         // Memoization: Avoid recalculating the same state
    
19.         String key = left + "," + right + "," + k;
    
20.         if (memo.containsKey(key)) return memo.get(key);
    
21. 
    
22.         boolean result;
    
23.         if (s.charAt(left) == s.charAt(right)) {
    
24.             // If characters match, move both pointers inward
    
25.             result = isValid(s, left + 1, right - 1, k);
    
26.         } else {
    
27.             // If characters don't match, try removing either left or right
    
28.             result = isValid(s, left + 1, right, k - 1) ||
    
29.                      isValid(s, left, right - 1, k - 1);
    
30.         }
    
31. 
    
32.         // Store the result in the memo map and return
    
33.         memo.put(key, result);
    
34.         return result;
    
35.     }
    
36. 
    
37.     public static void main(String[] args) {
    
38.         Solution solution = new Solution();
    
39.         System.out.println(solution.validPalindrome("abca", 1)); // true
    
40.         System.out.println(solution.validPalindrome("abcdeca", 2)); // true
    
41.         System.out.println(solution.validPalindrome("abcdef", 1)); // false
    
42.     }
    
43. }
    

复制代码

感谢分享，已加米，请问是不是E4 Infra岗，SD dive deep的时候要答得很全面？

follow up 是1216题吗 谢谢zszs

follow up 斯领留 这题题号是对的?

say543 发表于 2024-10-30 08:21
follow up 斯领留 这题题号是对的?

同问。。是不是写错了，这题不是tag，而且用树状数组貌似也不是卖塔考察范围吧