Проверка того, что одна строка является перестановкой другой в C++

Question

Я работал над некоторыми вопросами программирования, чтобы попытаться обновить мою память структурами данных и алгоритмами. Проблема заключается в проверке, является ли одна строка перестановкой другой.

Множество программных решений, которые я видел, сортирует каждую строку, а затем проверяет, соответствуют ли отсортированные строки друг другу. Обычно это делается путем делать что-то вроде этого:

sort(strOne.begin(), strOne.end()); 
sort(strTwo.begin(), strTwo.end()); 

for (int i = 0; i < strOne.length(); i++) 
    { 
     if (strOne[i] != strTwo[i]) 
     { 
      return false; 
     } 
    } 

Однако, мне интересно, если после сортировки строк вы могли бы просто сравнить строки непосредственно вместо того, чтобы использовать для цикла. Например,

 if (strOne == strTwo) { 
    return true; 
} 

Есть ли что-то, что у меня отсутствует, в котором второй вариант не работает? Я чувствую, что у меня отсутствует базовая концепция, потому что кажется, что большинство решений имеют цикл for для итерации строки.

Заранее благодарен!

Answer 1

Вы можете использовать str1.compare (str2), который будет сравнивать строки лехографически и возвращать 0, если они равны.

Но, ваше решение принимает O (NlogN) сложность и она может быть решена за линейное время ...

Answer 2

Пожалуйста, явно возвращает истину или ложь во всех возможных условиях. В противном случае вы не можете получить желаемый результат.

В первом блоке кода у вас нет значения возврата, определенного вне цикла for. Итак, явно ваша функция ничего не вернет, если две строки равны.

Во втором блоке кода у вас нет значения возврата, определенного вне оператора if. Итак, явно ваша функция ничего не вернет, если две строки не равны.

Answer 3

СТЛ путь:

std::string str0, str1; 
bool IsPermutation = std::is_permutation(str0.begin(), str0.end(), str1.begin(), str1.end()); 

Answer 4

Да, вы можете непосредственно сравнить строку. Correcct способ использовать сравнение строк в функции будет

return str1 == str2; 

окольным путем

if (str1 == str2) { 
    return true; 
} 
else { 
    return false; 
} 

имеет серьезные недостатки: он несколько раз дольше, это легко забыть else часть (вы только что сделали) , и во время рефакторинга его легче сломать.

Answer 5

std::sort(strOne.begin(), strOne.end()); 
std::sort(strTwo.begin(), strTwo.end());  
return strOne == strTwo; 

будет достаточным.

---

Мое предложение заключается в использовании std::unordered_map

т.е.

std::unordered_map< char, unsigned > umapOne; 
std::unordered_map< char, unsigned > umapTwo; 
for(char c : strOne) ++umapOne[c]; 
for(char c : strTwo) ++umapTwo[c]; 
return umapOne == umapTwo; 

---

В качестве оптимизации вы можете добавить в верхней части для решения

if(strOne.size() != strTwo.size()) return false; 

---

std::unordered_map Лучше раствора,

if(strOne.size() != strTwo.size()) return false; // required 
std::unordered_map< char, int > umap; 
for(char c : strOne) ++umap[c]; 
for(char c : strTwo) if(--umap[c] < 0) return false; 
return true; 

---

Если вам нужно просто решить проблему, не зная, как это сделать, вы можете использовать std::is_permutation

return std::is_permutation(strOne.begin(), strOne.end(), strTwo.begin(), strTwo.end()); 

Answer 6

Просто, чтобы дополнить другие ответы, если вы знаете, априорно диапазон символов обеих строк ('а '-' z ') или что-то подобное этому, тогда вы можете решить проблему в линейном времени. Может быть, хорошо решить эту проблему в O (n log n), но это не всегда так.

Здесь была бы моя версия для решения этой проблемы. Он использует тот факт, что если оба слова имеют одинаковую частоту для каждого символа, то можно переставить в другую.

#include <string> 
#include <vector> 
#include <map> 
#include <iostream> 

using namespace std; 

int main() 
{ 
    string a, b; 
    cin >> a >> b; 
    vector<int> frequencyOfLettersA(26, 0); 
    vector<int> frequencyOfLettersB(26, 0); 

    for(char c : a) 
     frequencyOfLettersA[c - 'a']++; 
    for(char c : b) 
     frequencyOfLettersB[c - 'a']++; 

    bool isPermutation = true; 
    for(int i = 0; i < 26; ++i) 
    { 
     if(frequencyOfLettersA[i] != frequencyOfLettersB[i]) 
     { 
      isPermutation = false; 
      break; 
     } 
    } 
    if(isPermutation) 
     cout << "Yes" << endl; 
    else 
     cout << "No" << endl; 
}