Цель алгоритма анаграммы

Question

Я написал следующий код для проверки анаграммы, хочу знать, это идеально и есть ли лучший способ реализовать то же самое в цели C

-(BOOL) findAnagram :(NSString *) string1 :(NSString *) string2
{
    int len = string1.length;
    if (len != string2.length)
    {
        return false;
    }

    for (int i=0; i < len; i++)
    {
        int h = 0;
        int q = 0;
        for (int k = 0;  k < len ; k ++)
        {
            if ([string1 characterAtIndex:i] == [string1 characterAtIndex:k])
            {
                h++;
            }
            if ([string1 characterAtIndex:i] == [string2 characterAtIndex:k])
            {
                q++;
            }
        }

        if (h!=q)
        {
            return false;
        }
    }
    return TRUE;
}

Answer 1

Более эффективная версия, чем ваша, которая является алгоритмом O(n ^ 2), является алгоритмом O(n):

BOOL anagrams(NSString *a, NSString *b)
{
    if (a.length != b.length)
        return NO;

    NSCountedSet *aSet = [[NSCountedSet alloc] init];
    NSCountedSet *bSet = [[NSCountedSet alloc] init];

    for (int i = 0; i < a.length; i++)
    {
        [aSet addObject:@([a characterAtIndex:i])];
        [bSet addObject:@([b characterAtIndex:i])];
    }

    return [aSet isEqual:bSet];
}

Answer 2

Вы хотите знать, если две строки содержат одинаковые символы? Проще всего было бы отсортировать их обоих и сравнить отсортированную версию.

Другой способ - подсчитать количество появлений каждой буквы (сколько As, сколько B и т. Д.), А затем сравнить эти значения.

(Примечание: второй способ - это просто вариант первого, это один из эффективных способов сортировки строки)

Answer 3

Это выглядит хорошо для меня. Но стиль кода немного странный. Я бы написал это так:

- (BOOL)isStringAnagram:(NSString *)string1 ofString:(NSString *)string2 {
    int len = string1.length;
    if (len != string2.length) {
        return NO;
    }

    for (int i=0; i < len; i++) {
        int h = 0;
        int q = 0;
        for (int k = 0;  k < len; k++) {
            if ([string1 characterAtIndex:i] == [string1 characterAtIndex:k]) {
                h++;
            }
            if ([string1 characterAtIndex:i] == [string2 characterAtIndex:k]) {
                q++;
            }
        }

        if (h != q) {
            return NO;
        }
    }

    return YES;
}

Основная проблема у меня с именем метода. Хотя в названии могут быть параметры, которые не имеют ничего перед ними, это не рекомендуется. то есть вы имели findAnagram:: как имя, тогда как я использовал isStringAnagram:ofString:,

Answer 4

Еще один запуск алгоритма мельницы:

- (BOOL) testForAnagramWithStrings:(NSString *)stringA andStringB: (NSString *)stringB{

    stringA = [stringA lowercaseString];

     stringB = [stringB lowercaseString];


     int counter = 0;

     for (int i=0; i< stringA.length; i++){


         for (int j=0; j<stringB.length;j++){


             if ([stringA characterAtIndex:i]==[stringB characterAtIndex:j]){

                 counter++;

             }


         }

     }

     if (counter!= stringA.length){

         return false;
     }

     return true;

}

Answer 5

Это реализация @zmbq, предлагающая сортировку и сравнение.

Вы должны учитывать требования удаления пробелов и быть нечувствительными к регистру.

- (BOOL)isAnagram:(NSString *)leftString and:(NSString *)rightString {
  NSString *trimmedLeft = [[leftString stringByReplacingOccurrencesOfString:@" " withString:@""] lowercaseString];
  NSString *trimmedRight = [[rightString stringByReplacingOccurrencesOfString:@" " withString:@""] lowercaseString];
  return [[self stringToCharArraySorted:trimmedLeft] isEqual:[self stringToCharArraySorted:trimmedRight]];
}

- (NSArray *)stringToCharArraySorted:(NSString *)string {
  NSMutableArray *array = [[NSMutableArray alloc] init];
  for (int i = 0 ; i < string.length ; i++) {
    [array addObject:@([string characterAtIndex:i])];
  }
  return [[array sortedArrayUsingSelector:@selector(compare:)] copy];
}

называется так

BOOL isAnagram = [self isAnagram:@"A BC" and:@"cba"];

Answer 6

Проверьте следующий метод, который проверяет строки Anagram.

- (BOOL) checkAnagramString: (NSString *) string1 WithAnotherString: (NSString *) string2 {

NSCountedSet *countSet1=[[NSCountedSet alloc]init];
NSCountedSet *countSet2=[[NSCountedSet alloc]init];

if (string1.length!=string2.length) {
    NSLog(@"NOT ANAGRAM String");
    return NO;
}


for (int i=0; i<string1.length; i++) {
    [countSet1 addObject:@([string1 characterAtIndex:i])];
    [countSet2 addObject:@([string2 characterAtIndex:i])];
}

if ([countSet1 isEqual:countSet2]) {
    NSLog(@"ANAGRAM String");
    return YES;
}
else{
    NSLog(@"NOT ANAGRAM String");
    return NO;

}

}