5. Longest Palindromic Substring

LeetCode Problems Solutions

question description: 问题描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给定一个字符串s，在s中找到最长的回文子串，你可以假设s的最大长度是1000。
字符串的回文:简单理解就是，字符串从前往后读 与 从后往前读 是一样的，也就是中心对称。
Example:例如

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.


Input: "cbbd"

Output: "bb"

solution with java - Java解决方案

提交结果：Time Limit Exceeded.
方法没有问题，可能对于非常长的字符串存在计算时间较长的问题，当然、所谓的时间长只不过是站在算法的角度来说的。

public String longestPalindrome(String s) {

        String result = "";

        char[] characters = s.toCharArray();

        for (int i = 0; i < s.length(); i++){


            String tmpStr = s.substring(i);
            
            if (result.length() >= tmpStr.length()) return result;
            
            
            while (tmpStr.length() > 0 ) {

                boolean isReverse = isReverseMethod(tmpStr);

                if (isReverse) {//是回文

                    if (result.length() < tmpStr.length()) {
                        result = tmpStr;
                    }

                    break;
                }

                tmpStr = tmpStr.substring(0,tmpStr.length() - 1);
                
            }
            
            
            

//             for (int j = tmpStr.length(); j >= 0 ; j--){

//                 String orderStr = tmpStr.substring(0,j);

//                 boolean isReverse = isReverseMethod(orderStr);

//                 if (isReverse){//是回文

//                     if (result.length() < orderStr.length()){
//                         result = orderStr;
//                     }

//                     break;
//                 }

//             }

        }

        return result;

    }

    //判断一个字符串是否是回文
    private static boolean isReverseMethod(String orderStr){


//         String reverseStr = "";
//         char[] charArray = orderStr.toCharArray();

//         for (int i=charArray.length-1; i>=0; i--){
//             reverseStr += charArray[i];
//         }

//         if (orderStr.equals(reverseStr)){
//             return true;
//         }

//         return false;
        

        boolean result = true;
        char[] charArray = orderStr.toCharArray();
        int length = charArray.length;

        for (int i=length-1; i>= length / 2; i--) {

            char start = charArray[i];
            char end = charArray[length - i - 1];
            if (start != end) {
                result = false;
                break;
                
            }
        }


        return result;
    }

solution with swift - swift解决方案

提交结果：Time Limit Exceeded.
方法没有问题，可能对于非常长的字符串存在计算时间较长的问题，当然、所谓的时间长只不过是站在算法的角度来说的。

func longestPalindrome(_ s: String) -> String {
    
        var result = "";
        var start = 0;
        
        for _ in s.characters{
            
            
            var tmpStr = s.substring(from: s.index(s.startIndex, offsetBy: start))
            
            start += 1
            
            while tmpStr.characters.count > 0 {
                
                
                let isReverse = isReverseMethod(tmpStr);
                
                if (isReverse){//是回文
                    
                    if (result.characters.count < tmpStr.characters.count){
                        result = tmpStr;
                    }
                    break
                }
                
                
                tmpStr = tmpStr.substring(to: tmpStr.index(tmpStr.endIndex, offsetBy: -1))
            }
            
//            var orderStr = ""
            
//            for indexChar in tmpStr.characters{
//                
//                orderStr = orderStr + "\(indexChar)"
//                
//                let isReverse = isReverseMethod(orderStr);
//                
//                if (isReverse){//是回文
//                    
//                    if (result.characters.count < orderStr.characters.count){
//                        result = orderStr;
//                    }
//                
//                }
//                
//            }
            
        }
        
        return result;
    
    }
    
    //判断一个字符串是否是回文
    func isReverseMethod(_ orderStr : String)->Bool{
    
        var orderString = ""
        var reverseStr = ""
       
        for char in orderStr.characters{
            
            orderString = orderString + "\(char)"
            reverseStr = "\(char)" + reverseStr
   
        }
        
        if orderString.compare(reverseStr) == .orderedSame {
            return true
        }
        
        return false

    }