Anagrams

Description

Write a method to decide if two strings are anagrams or not.

Tips:

  • Confirm is it only about one word, or the string could be like a sentence with multiple spaces.
  • The occurrence of certain character in anagrams is same.
  • One method is judge it by comparing the occurrence of each character in two strings.
  • Another option could be sort both strings first, then compare the two sorted string, anagrams will be the same after being sorted.

Pseudo-code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

open up a fixed sized array, representing the occurrence of each character
for(each character in string1)
{
  array[character]++;//count the occurrence
}
for(each character in string2)
{
  array[character]--;//count the occurrence
}
for(array)
{
  if all items == 0;
      return YES;
  else
      return NO;
}

My Objective-C Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 Time complexity: O(2n)
 Space: O(256)
 */
- (BOOL) isAnagram1_4:(NSString *)s1
           withString:(NSString *)s2
{
    if (nil == s1 || nil == s2 || [s1 length] != [s2 length] || [s1 isEqualToString:s2]) return NO;

    int assic[256];
    memset(assic, 0, sizeof(assic));

    for (int n = 0; n < [s1 length]; n++)
    {
        assic[[s1 characterAtIndex:n]]++;
    }

    for (int m = 0; m < [s2 length]; m++)
    {
        assic[[s2 characterAtIndex:m]]--;
    }

    for (int loop = 0; loop < 256; loop ++)
    {
        if (assic[loop] != 0)
            return NO;
    }
    return YES;
}

My Objective-C Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 Time complexity: O(2nlogn)
 Space: O(2n)
 */
- (BOOL) isAnagram1_4_2:(NSString *)s1
             withString:(NSString *)s2
{
    if (nil == s1 || nil == s2 || [s1 length] != [s2 length] || [s1 isEqualToString:s2]) return NO;

    char string1[[s1 length] + 1];
    memccpy(string1, [s1 UTF8String], sizeof(char), [s1 length] + 1);
    char string2[[s2 length] + 1];
    memccpy(string2, [s2 UTF8String], sizeof(char), [s2 length] + 1);

    sort(&string1[0], &string1[0] + [s1 length]);
    sort(&string2[0], &string2[0] + [s2 length]);

    printf("string1 sorted = %s \n", string1);
    printf("string2 sorted = %s \n", string2);



    return strcmp(string1, string2) == 0;
}

Test the Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

- (void)viewDidLoad
{
    [super viewDidLoad];

    NSString *s1 = @"abcde";
    NSString *s2 = @"ecbda";
    NSString *s3 = @"sdfdf";
    NSString *s4 = @"abababc";
    NSString *s5 = @"ccccc";

    NSLog(@"ret = %d", [self isAnagram1_4:s1 withString:s2]);
    NSLog(@"ret = %d", [self isAnagram1_4:s2 withString:s3]);
    NSLog(@"ret = %d", [self isAnagram1_4:s3 withString:s4]);
    NSLog(@"ret = %d", [self isAnagram1_4:s4 withString:s5]);

}

Comments