Cracking the coding interview--Q8.4

제목
원문:
Write a method to compute all permutations of a string.
번역문:
문자열의 모든 배열을 되돌려주는 방법을 쓰십시오.
해답
분명히 길이가 n인 줄의 전체 배열은 모두 A(n, n)=n!종, 귀속적인 방법으로 풀고 문자열이'abc'이면 함수는recursionPermu이고 서로 다른 귀속 사고방식으로 분석한다.
해법 1:
0자 문자 a를 꺼내서 recursionPermu를 차례로 호출하여 나머지 "bc"의 모든 배열을 구합니다. "bc", "cb"입니다. 이 문자열을 각각 삽입하여 모든 배열을 얻을 수 있습니다. abc,bac,bca,acb,cab,cba, 코드는 다음과 같습니다.

public static LinkedList<String> recursionPermu(String str){
		LinkedList<String> result=new LinkedList<String>();
		if(str.equals("")){
			result.add("");
			return result;
		}
		String c=str.substring(0,1);
		LinkedList<String> res=recursionPermu(str.substring(1));
		for(int i=0;i<res.size();++i){
			String t=res.get(i);
			for(int j=0;j<=t.length();++j){
				String u=t;
				u=insertStr(u,j,c);
				result.add(u);
			}
		}
		return result;
	}
	// 
	public static String insertStr(String target,int index,String str){
		String targetStr="";
		if(index==0) targetStr=str+target;
		else if(index==target.length()) targetStr=target+str;
		else  targetStr=target.substring(0,index)+str+target.substring(index);
		return targetStr;
	}

해법 2:
또한 문자열의 모든 문자를 순서대로 추출한 다음recursionPermu로 나머지 열의 배열수를 구하고 배열마다 이 문자를 추가하면 된다. 예를 들어 abc, acb, bac, bca,cab, cba, 코드는 다음과 같다.

public static LinkedList<String> recursionPermu1(String str){
		LinkedList<String> result=new LinkedList<String>();
		if(str.equals("")){
			result.add("");
			return result;
		}
		for(int i=0;i<str.length();++i){
			String c=str.charAt(i)+"";
			String t=str;
			LinkedList<String> res=recursionPermu1(eraseStr(t,i));
			for(int j=0;j<res.size();++j){
				result.add(c+res.get(j));
			}
		}
		return result;
	}
	// 
	public static String eraseStr(String str,int index){
		if(str.equals("")) return "";
		if(index==0) return str.substring(1);
		if(index==str.length()-1) return str.substring(0,str.length()-1);
		else return str.substring(0,index)+str.substring(index+1);
	}

전체 코드는 다음과 같습니다.

import java.util.LinkedList;

class Q8_4{
	public static LinkedList<String> recursionPermu(String str){
		LinkedList<String> result=new LinkedList<String>();
		if(str.equals("")){
			result.add("");
			return result;
		}
		String c=str.substring(0,1);
		LinkedList<String> res=recursionPermu(str.substring(1));
		for(int i=0;i<res.size();++i){
			String t=res.get(i);
			for(int j=0;j<=t.length();++j){
				String u=t;
				u=insertStr(u,j,c);
				result.add(u);
			}
		}
		return result;
	}
	// 
	public static String insertStr(String target,int index,String str){
		String targetStr="";
		if(index==0) targetStr=str+target;
		else if(index==target.length()) targetStr=target+str;
		else  targetStr=target.substring(0,index)+str+target.substring(index);
		return targetStr;
	}

	public static LinkedList<String> recursionPermu1(String str){
		LinkedList<String> result=new LinkedList<String>();
		if(str.equals("")){
			result.add("");
			return result;
		}
		for(int i=0;i<str.length();++i){
			String c=str.charAt(i)+"";
			String t=str;
			LinkedList<String> res=recursionPermu1(eraseStr(t,i));
			for(int j=0;j<res.size();++j){
				result.add(c+res.get(j));
			}
		}
		return result;
	}
	// 
	public static String eraseStr(String str,int index){
		if(str.equals("")) return "";
		if(index==0) return str.substring(1);
		if(index==str.length()-1) return str.substring(0,str.length()-1);
		else return str.substring(0,index)+str.substring(index+1);
	}

	public static void main(String[] args){
		String s="abc";
		LinkedList<String> res=recursionPermu(s);
		for(int i=0;i<res.size();i++){
			System.out.println(res.get(i));
		}
		System.out.println("");

		LinkedList<String> res1=recursionPermu1(s);
		for(int i=0;i<res1.size();i++){
			System.out.println(res1.get(i));
		}
	}
}

---EOF---