Цель алгоритма анаграммы
Я написал следующий код для проверки анаграммы, хочу знать, это идеально и есть ли лучший способ реализовать то же самое в цели 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;
}
4 ответа
Более эффективная версия, чем ваша, которая является алгоритмом 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];
}
Вы хотите знать, если две строки содержат одинаковые символы? Проще всего было бы отсортировать их обоих и сравнить отсортированную версию.
Другой способ - подсчитать количество появлений каждой буквы (сколько As, сколько B и т. Д.), А затем сравнить эти значения.
(Примечание: второй способ - это просто вариант первого, это один из эффективных способов сортировки строки)
Это выглядит хорошо для меня. Но стиль кода немного странный. Я бы написал это так:
- (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:
,
Еще один запуск алгоритма мельницы:
- (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;
}
Это реализация @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"];
Проверьте следующий метод, который проверяет строки 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;
}
}