题目

给一个字符串，求出最长的回文串。我考虑使用一个栈，通过压栈弹栈来完成。

解法

public static void main(String[] args) {        String s = "PATZJUJZTACCBCCA";        Stack
    
      stack = new Stack<>();        for(int i=0;i
     
       copy = new Stack<>();                copy.addAll(stack);                handleSplitEven(copy,i,s);            }            if(i>1&&stack.peek()!=s.charAt(i)&&stack.get(i-2) == s.charAt(i)){                //次栈顶元素和即将添加的元素一样，回文串出现，分裂                Stack
      
        copy = new Stack<>();                copy.addAll(stack);                handleSplitOdd(copy,i,s);            }            stack.push(s.charAt(i));        }    }    //偶数型回文串    private static void handleSplitEven(Stack
       
         copy, int i, String s) {        copy.push(s.charAt(i));        String target = ""+copy.pop()+copy.pop();        System.out.println(target);        i++;        for(;i
        
          0;i++){            if(copy.peek() == s.charAt(i)){                target = copy.pop()+target+s.charAt(i);                System.out.println(target);            }else{                break;            }        }    }    //奇数型回文串    private static void handleSplitOdd(Stack
         
           copy, int i, String s) { char center = copy.pop(); String target = ""+copy.pop()+center+s.charAt(i); System.out.println(target); i++; for(;i
          
           0;i++){ if(copy.peek() == s.charAt(i)){ target = copy.pop()+target+s.charAt(i); System.out.println(target); }else{ break; } } }
          
         
        
       
      
     
    

输出结果

JUJZJUJZTZJUJZTATZJUJZTACCCBCCCBCCACCBCCACC

复杂度分析