I Am Able To Go Out Array Bounds

Question

Учитывая две строки, напишите метод, чтобы решить, является ли это анаграммой/перестановкой другой. Это мой подход:

Я написал эту функцию, чтобы проверить, являются ли 2 строки анаграммами (такими как собака и бог).

В ASCII, а до г составляет 97 - 122.

В основном я есть массив BOOLS, которые все изначально ложными. Каждый раз, когда я сталкиваюсь с символом в строке string1, он обозначает его как true.

Чтобы проверить, является ли его анаграмма, я проверяю, являются ли какие-либо символы строки2 ложными (должно быть истинным, если встречается в строке1).

Я не уверен, как это работает: arr [num] = true; (не должен работать, потому что я не принимаю во внимание, что ascii начинается с 97 и, следовательно, выходит за пределы).

(Примечание стороны: есть лучший подход, чем у меня)

EDIT: Спасибо за все ответы! Будем внимательно читать каждый. Кстати: не задание. Это проблема из кодирования интервью практики книги

bool permutation(const string &str1, const string &str2) 
{ 
    // Cannot be anagrams if sizes are different 
    if (str1.size() != str2.size()) 
     return false; 

    bool arr[25] = { false }; 

    for (int i = 0; i < str1.size(); i++) // string 1 
    { 
     char ch = (char)tolower(str1[i]); // convert each char to lower 
     int num = ch; // get ascii 
     arr[num-97] = true; 
    } 

    for (int i = 0; i < str2.size(); i++) // string 2 
    { 
     char ch = (char)tolower(str2[i]); // convert char to lower 
     int num = ch; // get ascii 
     if (arr[num-97] == false) 
      return false; 
    } 

    return true; 
} 

Answer 1

Там нет встроенных в массивах C++, что мешает вам писать и после окончания их. Но при этом вы нарушаете контракт, который у вас есть с компилятором, и поэтому он может делать все, что пожелает (неопределенное поведение).

Вы можете получить проверку границ на «массивах», используя класс vector, если это то, что вам нужно.

Что касается лучшего подхода, то, вероятно, лучше, если ваш массив достаточно большой, чтобы покрыть каждый возможный символ (так что вам не нужно беспокоиться о проверке границ), и это не должно быть значением истины как счетчик, чтобы обрабатывать повторяющиеся символы внутри строк. Если это просто значение истины, то here и her будут считаться анаграммами.

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

def isAnagram (str1, str2): 
    # Different lengths means no anagram. 

    if len(str1) not equal to len(str2): 
     return false 

    # Initialise character counts to zero. 

    create array[0..255] (assumes 8-bit char) 
    for each index 0..255: 
     set count[index] to zero 

    # Add 1 for all characters in string 1. 

    for each char in string1: 
     increment array[char] 

    # Subtract 1 for all characters in string 2. 

    for each char in string2: 
     decrement array[char] 

    # Counts will be all zero for an anagram. 

    for each index 0..255: 
     if count[index] not equal to 0: 
      return false 
    return true 

Answer 2

Да, C и C++ и не проводить index-out-of-bounds.

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

Улучшенный код:

bool permutation(const string &str1, const string &str2) 
{ 
    // Cannot be anagrams if sizes are different 
    if (str1.size() != str2.size()) 
     return false; 

    int arr[25] = { 0 };     //<-------- Changed 

    for (int i = 0; i < str1.size(); i++) // string 1 
    { 
     char ch = (char)tolower(str1[i]); // convert each char to lower 
     int num = ch; // get ascii 
     arr[num-97] += 1;     //<-------- Changed 
    } 

    for (int i = 0; i < str2.size(); i++) // string 2 
    { 
     char ch = (char)tolower(str2[i]); // convert char to lower 
     int num = ch; // get ascii 
     arr[num-97] = arr[num-97] - 1 ; //<-------- Changed 
    } 

    for (int i =0; i< 25; i++) {   //<-------- Changed 
     if (arr[i] != 0) {    //<-------- Changed 
      return false;     //<-------- Changed 
     } 
    }  
    return true; 
} 

Answer 3

Работая подход: с нуля за дополнительную плату.

bool permutation(const std::string &str1, const std::string &str2) 
{ 
    // Cannot be anagrams if sizes are different 
    if (str1.size() != str2.size()) 
     return false; 

    int arr[25] = {0 }; 

    for (int i = 0; i < str1.size(); i++) // string 1 
    { 
     char ch = (char)tolower(str1[i]); // convert each char to lower 
     int num = ch; // get ascii 
     arr[num-97] = arr[num-97] + 1 ; 
    } 

    for (int i = 0; i < str2.size(); i++) // string 2 
    { 
     char ch = (char)tolower(str2[i]); // convert char to lower 
     int num = ch; // get ascii 
     arr[num-97] = arr[num-97] - 1 ; 
    } 

    for (int i =0; i< 25; i++) { 
     if (arr[i] != 0) { 
      return false; 
     } 
    } 

    return true; 
}