java-颠倒一个句子中的词的顺序。比如： I am a student颠倒后变成：student a am I

public class ReverseWords {

	/**
	 * 题目：颠倒一个句子中的词的顺序。比如： I am a student颠倒后变成：student a am I.词以空格分隔。
	 * 要求：
	 * 1.实现速度最快,移动最少
	 * 2.不能使用String的方法如split,indexOf等等。
	 * 解答：两次翻转。
	 */
	public static void main(String[] args) {
		String str="  ^busy living, or busy     dying! $ ";
		str=reverseWords(str);
		System.out.println(str);
	}

	/*
	 Because we cannot use "String.split" to get each single word,
	 we use 'head' index and 'tail' index to find a word
	 Note that there're two cases in finding tail:	
	 1.current char is not ' ' and next char is ' ' 
	 2.current char is the end of string
	 */
	public static String reverseWords(String str){
		if(str==null){
			return null;
		}
		int length;
		if((length=str.length())==0 || length==1){
			return str;
		}
		char[] letters=str.toCharArray();
		int begin=-1;
		int end=-1;
		boolean hasBegined=false;
		boolean hasEnded=false;
		for(int i=0,len=str.length();i<len-1;i++){
		
			if(letters[i]!=' '){
				if(!hasBegined){
					begin=i;
					hasBegined=true;
				}else{
					if(letters[i+1]==' '){//case 1
						end=i;
						hasEnded=true;
					}
					if(i==len-2&&letters[i+1]!=' '){//case 2
						end=i+1;
						hasEnded=true;
					}
					if(hasEnded){
						reverseOneWord(letters,begin,end);//reverse each single word
						hasBegined=false;
						hasEnded=false;
					}
				}
			}
		}
		reverseOneWord(letters,0,str.length()-1);//reverse the whole string
		return new String(letters,0,str.length());
	}
	
	//reverse a single word
	public static void reverseOneWord(char[] letters,int begin,int end){
		if(letters==null||letters.length<2){
			return;
		}
		int len=letters.length;
		if(begin>=0&&begin<len&&end>=0&&end<len){
			while(begin<end){
				/*swap solution 1
				char tmp=letters[begin];
				letters[begin]=letters[end];
				letters[end]=tmp;
				*/
				//swap solution 2
				letters[begin]^=letters[end];
				letters[end]^=letters[begin];
				letters[begin]^=letters[end];
				begin++;
				end--;
			}
		}
	}
}

评论

1 楼 liang1022 2012-04-14  

搞的如此複雜，有什麼意義嗎?為什麼不能用String 方法?