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中找到最長的回文子串，你可以假設(shè)s的最大長度是1000渊抄。
字符串的回文:簡單理解就是，字符串從前往后讀 與 從后往前讀 是一樣的氧卧，也就是中心對稱或舞。
Example:例如
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"
solution with java - Java解決方案
提交結(jié)果：Time Limit Exceeded.
方法沒有問題，可能對于非常長的字符串存在計算時間較長的問題攻询，當(dāng)然低葫、所謂的時間長只不過是站在算法的角度來說的详羡。
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解決方案
提交結(jié)果：Time Limit Exceeded.
方法沒有問題，可能對于非常長的字符串存在計算時間較長的問題嘿悬，當(dāng)然实柠、所謂的時間長只不過是站在算法的角度來說的。
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
}
