求大家帮忙啊，小弟算法不行

编写一个函数

class Solution { public int symmetryPoint(String S); }

从给出的字符串 S 中，找到并返回这样一个字符的下标（下标从 0 开始算）， 使得这个字符左边的子字符串，刚好与右边的子字符串相反 （但如果这样的字符不存在的话，返回 −1）。

例如，给出这样一个字符串

"racecar"

你的函数应该返回 3，因为对于下标为 3 的字符 e， 其左边相邻的子字符串是 "rac"， 而右边相邻的子字符串是 "car"。

注： 与空字符串（长度为 0 的字符串）相反的还是一个空字符串。

假定:

• S 长度范围 [0..2,000,000].

复杂度:

• 最坏-情况下，期望的时间复杂度是 O(length(S));
• 最坏-情况下，期望的空间复杂度是 O(1) (不计输入参数所需的存储空间).

评论

12 楼 gao_xianglong 2013-03-09  

，期望的时间复杂度是 O

duoduodeai 写道

gao_xianglong 写道

public class Solution {
	public static int symmetryPoint(String s) {
		if (s.length() % 2 != 0) {
			String leftValue = "";
			String rightValue = "";
			String str = String.valueOf(s.charAt(s.length() / 2));
			String[] split = s.split(str);
			for (int i = split[0].length() - 1; i >= 0; i--)
				leftValue += split[0].charAt(i);
			rightValue = split[1];
			if (leftValue.equals(rightValue))
				return s.indexOf(str);
			else
				return -1;
		} else
			return -1;
	}

	public static void main(String[] args) {
		System.out.println(symmetryPoint("aa21eaxae12aa"));
	}
}

这个对，这个达到要求了

如果你对时间复杂度有要求，可以用如下：

import java.util.Date;

public class Solution {
	public static int symmetryPoint(String s) {
		if (s.length() % 2 != 0) {
			String leftValue = "";
			String rightValue = "";
			String str = String.valueOf(s.charAt(s.length() / 2));
			String[] split = s.split(str);
			// for (int i = split[0].length() - 1; i >= 0; i--)
			// leftValue += split[0].charAt(i);
			leftValue = String.valueOf(new StringBuffer(split[0]).reverse());
			rightValue = split[1];
			if (leftValue.equals(rightValue))
				return s.indexOf(str);
			else
				return -1;
		} else
			return -1;
	}

	public static void main(String[] args) {
		Date startTime = new Date();
		System.out.println(symmetryPoint("racqcar"));
		System.out.println("耗时：" + (new Date().getTime() - startTime.getTime())
				+ "毫秒");
	}
}

11 楼 duoduodeai 2013-03-09  

gao_xianglong 写道

public class Solution {
	public static int symmetryPoint(String s) {
		if (s.length() % 2 != 0) {
			String leftValue = "";
			String rightValue = "";
			String str = String.valueOf(s.charAt(s.length() / 2));
			String[] split = s.split(str);
			for (int i = split[0].length() - 1; i >= 0; i--)
				leftValue += split[0].charAt(i);
			rightValue = split[1];
			if (leftValue.equals(rightValue))
				return s.indexOf(str);
			else
				return -1;
		} else
			return -1;
	}

	public static void main(String[] args) {
		System.out.println(symmetryPoint("aa21eaxae12aa"));
	}
}

这个对，这个达到要求了

10 楼 duoduodeai 2013-03-09  

307813859 写道

public class Test {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
symmetryPoint("racecarar");
}

public static void symmetryPoint(String str){
int num = -1;
for(int i=1; i<str.length()-1; i++){
if(str.charAt(i-1) == str.charAt(i+1)){
System.out.println("-----"+i);
}
}
}

}

这个真没达到要求

9 楼 duoduodeai 2013-03-09  

先S必须是奇数才符合条件。

lsp1988 写道

首先S必须是奇数才符合条件。
先假定存在:
String stt =1;
for(int i=1,i<=(s.length（）-1）/2;i++){
   String a1 = s.charAt((s.length（）-1）/2-i);
   String b1 = s.charAt((s.length（）-1）/2+i);
   if(a1!=b1){
     stt=-1;
   }
}
if(stt =-1){
  则不存在;
}else{
  存在;
}


没上机跑过，大概就是这么个意思。

谢谢你提供的思路！！

8 楼 gao_xianglong 2013-03-09  

public class Solution {
	public static int symmetryPoint(String s) {
		if (s.length() % 2 != 0) {
			String leftValue = "";
			String rightValue = "";
			String str = String.valueOf(s.charAt(s.length() / 2));
			String[] split = s.split(str);
			for (int i = split[0].length() - 1; i >= 0; i--)
				leftValue += split[0].charAt(i);
			rightValue = split[1];
			if (leftValue.equals(rightValue))
				return s.indexOf(str);
			else
				return -1;
		} else
			return -1;
	}

	public static void main(String[] args) {
		System.out.println(symmetryPoint("aa21eaxae12aa"));
	}
}

7 楼 307813859 2013-03-09  

public class Test {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
symmetryPoint("racecarar");
}

public static void symmetryPoint(String str){
int num = -1;
for(int i=1; i<str.length()-1; i++){
if(str.charAt(i-1) == str.charAt(i+1)){
System.out.println("-----"+i);
}
}
}

}

6 楼 frank-liu 2013-03-08  

楼主应该注意到，这个问题主要就是判断给定的一个字符串是否对称。你可以用两个变量，比如l = 0, r = s.length - 1;他们分别指向字符串的头和尾。然后用一个循环比较它们两个的值是否相同，如果相同，则l++, r--，这样一直循环到l >= r。所以问题的核心就是这么一点：

while(l <= r) {
    if(!s.charAt(l).equals(s.charAt(r))) //如果不相等，则表示这个字符串根本就不是对称的，你也就不必要找了。
        return -1;
    l++;
    r--;
}
// 如果能够从这个循环里走出来
return l - 1;

5 楼 lsp1988 2013-03-08  

首先S必须是奇数才符合条件。
先假定存在:
String stt =1;
for(int i=1,i<=(s.length（）-1）/2;i++){
   String a1 = s.charAt((s.length（）-1）/2-i);
   String b1 = s.charAt((s.length（）-1）/2+i);
   if(a1!=b1){
     stt=-1;
   }
}
if(stt =-1){
  则不存在;
}else{
  存在;
}


没上机跑过，大概就是这么个意思。

4 楼 duoduodeai 2013-03-08  

lsp1988 写道

lsp1988 写道

这很简单吧，无非就是计算出S的长度，然后左右index下比较是否相等即可。

说错了，是charAt（）；

不会

3 楼 lsp1988 2013-03-08  

lsp1988 写道

这很简单吧，无非就是计算出S的长度，然后左右index下比较是否相等即可。

说错了，是charAt（）；

2 楼 lsp1988 2013-03-08  

这很简单吧，无非就是计算出S的长度，然后左右index下比较是否相等即可。

1 楼 duoduodeai 2013-03-08  

麻烦各位高手不~吝~赐~教！！！！！！！！