objective-c - Anagram 算法目标 C

Question

我已经编写了以下代码来检查 anagram 想知道这是完美的吗？有没有更好的方法在目标 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

You want to know if two strings contain exactly the same characters? Easiest way would probably be to sort both of them and compare the sorted version.

Another way would be to count the number of appearances of each letter (how many As, how many Bs, and so forth), then compare those counts.

(Note: The second way is just a variation of the first one, it's one efficient way to sort a string)

Answer 3

It looks fine to me. But the code style is slightly odd. I would write it like this:

- (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;
}

The main issue I have is with the method name. While it's possible to have parameters that have nothing before them in the name, it is not advisable. i.e. you had findAnagram:: as the name whereas I've used isStringAnagram:ofString:.

Answer 4

这是对@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 5

磨坊算法的另一个运行：

- (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 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;
  }

}