如何證明兩個字符串是相互排列的？

我正在破解代碼面試書，我在數組和字符串章節中遇到了問題，他們要求編寫一個方法，證明給出的兩個字符串是相互排列的。如何證明兩個字符串是相互排列的？

書中的答案非常乾淨清晰。一種是排序，然後比較它們是否相同，另一種是檢查兩個字符串是否具有相同的字符數。

但是，我對這個問題採取了不同的方法，我想與您分享以查看您的意見。

我假定這些字符是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

如何證明兩個字符串是相互排列的？

回答

相關問題