首页 > 其他 > 详细

面试题之微软 字符串的所有排列

时间:2014-01-23 07:55:51      阅读:304      评论:0      收藏:0      [点我收藏+]

字符串的所有排列

  • 真言

交通发达才能发展,农村修路迫不及待。

  • 题目

给出一个函数来输出一个字符串的所有排列。

  • 思路

思路很简单,时间复杂度O(n*n),思路如下(对于还有相同字符的字符串,答案会有重复的,去重就好了)
  1. 保存一个空的字符串A,
  2. 对给定字符串B的每一个字符
  3. 插入A中,出入的位置有n(n为当前字符串A的长度)+1种情况
  4. 直至A的长度和B相同时,则输出A
举个例子,如下
给定字符串string=“bhe”
  1. bubuko.com,布布扣
  2. bubuko.com,布布扣
  3. bubuko.com,布布扣
  4. 对于三个字符,答案最多就是6个

  • 实验

bubuko.com,布布扣

  • 代码

test.cpp
#include <iostream>
#include <string>
#include <fstream>

using namespace std;

// function all orders
void All_orders(string A,string B,string::size_type n,ofstream &f);
// function randstring
string RandString();


// function main
int main()
{

	int i = 0;
	while(i<1)
	{
		ofstream f;
		f.open("txt.txt");
		string test = RandString();
		cout<<"test="<<test<<endl;
		All_orders("",test,0,f);
		f.close();
		i++;
	}

	system("pause");
	return 0;
}



// function all orders
void All_orders(string A,string B,string::size_type n,ofstream &f)
{
	if(n < B.length())
	{	
		string next = A;
		next = B[n] + A;
		All_orders(next,B,n+1,f);
		for(string::size_type i = 1;i < A.length();i++)
		{
			next  = A.substr(0,i)+B[n]+A.substr(i,A.length());
			All_orders(next,B,n+1,f);
		}
		if(A.length()>0)
		{
			next = A + B[n];
			All_orders(next,B,n+1,f);
		}
	}
	else if(n == B.length())
	{
		cout<<A<<" "<<endl;
		f<<A<<endl;
	}
}

// function randstring
string RandString()
{
	int size =  4;
	string result = "";
	for(int i = 0; i<size; i++)
	{
		result = result + (char)( ‘a‘ + rand()%10 );
	}
	return result ;
}


面试题之微软 字符串的所有排列

原文:http://blog.csdn.net/cqs_experiment/article/details/18676369

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!