查找兄弟单词(2012/5/6 百度实习笔试题)

时间:2023-01-24 14:39:29

一个单词字母交换,可得另一个单词,如army->mary,成为兄弟单词。提供一个单词,在字典中找到它的兄弟。描述数据结构和查询过程。

方法一:首先用全排列方法写出该单词的所有可能兄弟单词。如army有3×2×1=24种结果(还没有优化有相同字符或大写字母的情况),然后用每一个'兄弟单词'去和字典中的单词匹配,找到即为兄弟单词下面给出全排列算法的代码,最直接的就是用递归了

/**
* @param src
* @param start 起始位置索引
* @param end 结束位置索引
*/
public static void perm(String[] src,int start,int end){
if(start==end){//当只要求对数组中一个字母进行全排列时,只要按该数组输出即可
for(int i=0;i<=end;i++){
System.out.print(src[i]);
}
System.out.println();
}
else{//多个字母全排列
for(int i=start;i<=end;i++){
String temp=src[start];//交换数组第一个元素与后续的元素
src[start]=src[i];
src[i]=temp;
perm(src,start+1,end);//后续元素递归全排列
temp=src[start];//将交换后的数组还原
src[start]=src[i];
src[i]=temp;
}
}
}

将字典中的和‘比较单词’首字母相同的单词取出存放到一个数组中,将每一个组合和字典中的单词比较首先比较单词长度,长度相同,则继续比较;否则,比较下一个单词。算法如下:

 /**
* @param src 字典中的单词
* @param des 要比较的单词,因为要做大量比较,所以转化为字符数组
* @return
*/
public static boolean compare(String src,String[] des){
int len = src.length();
if(len != des.length){//如果长度不相等,肯定不是兄弟单词,则无需比较
return false;
}
int i = 1;//i等于1是因为首字符已经相同,无需比较
while(i<len){
if(des[i].equals(String.valueOf(src.charAt(i)))){
i++;
continue;
}
return false;
}
return true;
}
方法二:判断各自素数乘积是否相等(此思路来自http://blog.csdn.net/v_JULY_v/article/details/6347454)。

但对于本题,这个方法好像并不可行,但是可以作为一种思路去学习一下。


发散:排列组合算法的思路及代码:

本算法的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标
        代表的数被选中,为0则没选中。
        首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
        然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为
        “01”组合,同时将其左边的所有“1”全部移动到数组的最左端。
        当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得
        到了最后一个组合。
        例如求5中选3的组合:
        1  1  1  0  0  //1,2,3
        1  1  0  1  0  //1,2,4
        1  0  1  1  0  //1,3,4
        0  1  1  1  0  //2,3,4
        1  1  0  0  1  //1,2,5
        1  0  1  0  1  //1,3,5
        0  1  1  0  1  //2,3,5
        1  0  0  1  1  //1,4,5
        0  1  0  1  1  //2,4,5
        0  0  1  1  1  //3,4,5

 public static String[] getPortfolio(String[] numbers, int n) {
int m = numbers.length; //参数数组长度
int perm_count = 1; //构造数组长度标志
for (int s = m; s > m - n; s--)
{
perm_count *= s;
}
for (int z = n; z > 1; z--) { //获得排列数组长度perm_count
perm_count /= z;
}
String[] rs = new String[perm_count]; //新建一个存储字符排列的数组
String str = ""; //将第一种排列存入数组RS(即所有1都在左边的情况)
for (int x = 0; x < n; x++) {
str = str + numbers[x];
}
rs[0] = str;
int[] s = new int[m]; //构造下标数组
boolean flag = true; //循环开关
int k = 1; //返回结果数组长度(自增长)
for (int i = 0; i < m; i++) //初始化构造下标数组
{
if (i < n) {
s[i] = 1;
} else {
s[i] = 0;
}
}
do {
flag = false; //初始FLAG
int zerocount = 0; //10转换成01前的0的个数
for (int i = 0; i < m - 1; i++) {
if (s[i] == 0) { //记录前0个数(非0即1),可以通过这个参数进行1的前移
zerocount++;
}
if (s[i] == 1 && s[i + 1] == 0){ //10变成01
s[i] = 0;
s[i + 1] = 1;
flag = true; //如果成功转换,flag设置为true,如果没有转换,则1已经移动到最后,故可以跳出DO循环
for (int j = 0; j < i; j++) //10转换01前的所有1前移操作
{
if (j < i - zerocount) {
s[j] = 1;
} else {
s[j] = 0;
}
}
String returnstr = ""; //用于存储变化后的构造数组
for (int kk = 0; kk < m; kk++) //通过构造数组下标,得到需要的返回串
{
if (s[kk] == 1) {
returnstr += numbers[kk];
}
}
rs[k++] = returnstr; //将串存入RS数组,下标向后推一位,用于存储下个返回串
i = m; //转换了第一个10后,就要跳出该次FOR循环,所以将i直接置成m
}
}
} while (flag == true);
return rs;
}


作者:gaopo_Y

http://blog.csdn.net/gaopo_y/article/details/8082084