如何证明两个字符串是相互排列的？

我正在破解代码面试书，我在数组和字符串章节中遇到了问题，他们要求编写一个方法，证明给出的两个字符串是相互排列的。如何证明两个字符串是相互排列的？

书中的答案非常干净清晰。一种是排序，然后比较它们是否相同，另一种是检查两个字符串是否具有相同的字符数。

但是，我对这个问题采取了不同的方法，我想与您分享以查看您的意见。

我假定这些字符是ASCII字符。所以我在想的是首先检查两个字符串的长度是否相等，如果不是我们直接返回false，因为显然它反对排列的定义。

如果是这种情况，我们继续进行该算法。首先，我们初始化：

int sum = 0; 
int sum1 = 0;

然后我们遍历每个字符串添加的每个字符的总和的ASCII值和比较中端的款项的性质。如果他们是平等的，那么我们自己就是一个排列组合。

此方法是否有效？

来源

2014-06-11 Ralph

取而代之还有其他方法。您可以按字典顺序对字符串进行排序，并按字符进行比较。其他方法是找到两个字符串的每个字符的频率，然后比较它们。 –

不，这是行不通的，因为12是2和10两者之和的3和9的总和。

用你的算法"ad"可能是"bc"的排列组合。

在一般情况下，如果您允许合理的字符范围和字符串长度，那就没有真正的捷径。你提到的两个最好的解决方案取决于语言。

来源

2014-06-11 06:04:32

这很快，谢谢，还有13分钟，直到我给你一个绿色检查 – Ralph

dystroy是正确

得到它在99.999％的正确工作（由你的方法），你计算：

sum1 = sum (ASCII(i)) 
sum2 = sum (ASCII(i)^2) 
sum3 = sum (ASCII(i)^3)

两个字符串，如果都是一样的动力总和相同
，那么你必须最有可能置换串...

确定要比较直方图（如您提到的问题），但需要更多内存...

来源

2014-06-11 06:14:32 Spektre

这不能使用金额，因为一些不具备的独特之因素（如前面的答案中提到）

这可以通过比较字符直方图来完成实现

代码Java的

class Character_Histogram 
{ 
    public Map<Character,Integer> histogram; 

    public Character_Histogram() 
    { 
     histogram = new TreeMap<Character,Integer>(); 
    } 

    public void count (Character c) 
    { 
     if (histogram.containsKey(c)) 
      histogram.put(c, histogram.get(c)+1); 
     else 
      histogram.put(c, 1); 
    } 

    public void count (String str) 
    { 
     for(char c : str.toCharArray()) 
      count(new Character(c)); 
    } 
}

来源

2014-06-11 06:22:32

问题是关于是否有可能使用总和作比较。没有找到另一种方法来比较和顺便说一句，他已经表明，他知道如何计算（直方图=唯一的字符数） – Spektre

@Spektre你是对的 –

你的做法是行不通的，因为会有很多冲突中的款项，即基本上是假定你是为5 + 3 = 8，没有其他组合会产生8，但你是错误的例子4 + 4也是8。

有很多特设的方法来解决这个问题，我将描述其中两个。您可以使用质数来解决问题，方法与您的方法类似，或者只需分配2个数组并保留字符记录。

1.可以初始化2大小27的整数阵列，每个阵列说list1的[27]和list2中[27]初始化为0时，由字符阅读两个字符串字符说，如果你从串1读“C”，增加list1的第三个元素，因为'c'是第三个字符等，当你完成读取字符串时扫描两个数组中的不匹配，如果有任何不匹配，它们不是彼此的排列。

一种可能的实施方式可以是

char str1[50]="permutation"; 
char str2[50]="importunate"; 

int list1[27]={0},list2[27]={0}; 


for(int i=0;i<11;i++){ 
    list1[(int)str1[i]-(int)'a'+1]++; 
    list2[(int)str2[i]-(int)'a'+1]++; 
} 

for(int i=0;i<=27;i++){ 
    if(i==27){ 
     return true; 
    } 
    if(list1[i]!=list2[i]) 
    { 
     return false; 
    } 
}

此方法可以容易地扩展到考虑空间，不同的情况下，字符和数字。

2.这种方法类似于你做了什么，但使用的ASCII值，它使用质数和，而不是另外它采用乘法.Problem用你的方法是可能的冲突很多的，如果你作为dystroy指出选择乘法而不是你会再次面对同样的问题，但如果不乘以ascii值，我们乘以分配给特定字符的素数。

这里我们首先分配一个数组，它存储了从2开始的前26个素数，并且逐个字符地读取字符串并乘以所有分配给字符串的每个字符的相应素数，最后我们比较两个大整数，if这些都相等，则该字符串的相互

排列一个可能的实现可能是

int arr[27]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103}; 
char str1[50]="permutation"; 
char str2[50]="importunate"; 

int prd1=1,prd2=1; 


for(int i=0;i<11;i++){ 
    prd1=prd1*arr[(int)str1[i]-(int)'a']; 
    prd2=prd2*arr[(int)str2[i]-(int)'a']; 
} 

if(prd1==prd2) 
    return true; 

else 
    return false;

这种方法并不像第一个要扩展的，因为数字做大与字符串的长度，我们可以

prd1=prd1*arr[(int)str1[i]-(int)'a']%1000000009; 
prd2=prd2*arr[(int)str2[i]-(int)'a']%1000000009;//or some other large prime number

来源

2014-06-11 13:15:00

如何证明两个字符串是相互排列的？

回答

相关问题