確定字符串是否具有所有唯一字符

如何在不使用數組的情況下執行此操作？我有這個實現，但我需要做到這一點，而不使用數組，位操作和任何其他C/C++庫。確定字符串是否具有所有唯一字符

bool IsCharDuplication(string s) { 
    bool result = false; 
    bool controlArray[256]; 
    for (int i = 0; i < s.length(); i++) { 
    int val = s[i]; 
    if (controlArray[val] == true) { 
     result = true; 
     break; 
    } 
    controlArray[val] = true; 
    } 
    return result; 
}

來源

2013-04-13 ozdogan

這功課嗎？ – matt

nope，那是10年前我正在做作業:)只是一個棘手的c + +問題尋找替代方法。 – ozdogan

謝謝，只是對有趣的限制感到好奇。 – matt

使用兩個嵌套的循環：

bool IsCharDuplication(string s) 
{ 
for (int i = 0; i < s.length(); i++) 
    for (int j = i+1; j < s.length(); j++) 
     if (s[i] == s[j]) 
     return true; 
return false; 
}

注：你的算法有O（N）的時間，但我的解決方案爲O的時間（N^2）。

來源

2013-04-13 20:07:52 ahoo

你必須使用散列表（或散列集）來獲得O（n）的複雜性。以下實現使用按位操作，其中每個位對應字母表中的每個字符。

/** 
* Works for 0-127 ASCII string. Assuming, int is 16 bit. 
**/ 
int isduplicate(const char* str){ 
    int hash[8]={0,0,0,0,0,0,0,0}; 
    while(*str){ 
     int pos=*str; 
     if(hash[pos/16]&(1<<(pos%16))) 
      return 1; 
     hash[pos/16]|=(1<<(pos%16)); 
     str++; 
    } 
    return 0; 
}

來源

2013-04-14 03:11:10 faisal

使用此方法如果int爲64位，則只需要其中的2個（對於0-127）。如果你知道你的字符串只有a-z和A-Z，那麼你將需要2個32位int或1個64位int :) – faisal

OP要求做這個'不用數組，位操作'。儘管您的解決方案使用較小的陣列，但它仍然使用數組和位操作。 – Eran

Humm，我沒有看到位操作部分，對不起:( – faisal

您可以比其他答案中建議的O（N^2）算法做得更好。例如，您可以對O（NlogN）中的字符串進行快速排序或合併排序，並比對已排序的字符串執行單個傳遞來確定O（N）中是否有重複項。總的時間複雜度將是O（NlogN）。

bool IsCharDuplication (string s) 
{ 
    string s2 = sort(s); 
    for (int i = 0; i < s.length() - 1; i++) 
    if (s2[i] == s2[i+1]) 
     return true; 
    return false; 
}

我並沒有包括排序的字符串代碼，但你可以很容易找到這樣的代碼，寫自己的sort方法（因爲你不能使用C/C++庫）。

來源

2013-04-14 03:14:07 Eran

// ASCII assumed over unicode 
// O(n) algorithm 
// O(1) space 
bool isUnique(string s) { 
    // cannot exceed number of unique characters 
    if (s.length() > 256) return false; 
    bool checker[256]; 
    for (int i = 0; i < s.length(); i++) { 
     int val = s.at(i); 
     if (checker[val] == true) 
      return false; 
     checker[val] = true; 
    } 
    return true; 
}

來源

2016-05-10 01:45:13 blueman

什麼'int val = s.at（i）;'確實如此？ – Alex

@Alex它返回索引i處字符串的字符，然後將其轉換爲一個整數，你可以把它看作檢查器中的散列鍵，因爲每個字符都有它自己的唯一整數。 – blueman

確定字符串是否具有所有唯一字符

回答

相關問題