3

8 文字の単語のグループ内でアナグラムを見つけるアルゴリズムがあります。事実上、長い単語の文字をアルファベット順に並べ替え、短い単語を 1 つずつ同じようにして、長い単語にそれらが存在するかどうかを確認します。

tower = eortw two = otw rot = ort

ここでの問題は、私がortin eortw(または塔で腐敗) を探すと、問題なく見つかるということです。腐敗は塔の中にあります。ただし、中央に R があるため、otw内側eortw(またはタワー内の 2 つ) ではありません。したがって、2 つがタワーにあるとは考えられません。

これを行うためのより良い方法はありますか？私はObjective-Cでそれをやろうとしています.8文字の単語と通常の単語の両方がNSDictionaries(通常の形式とアルファベット順の形式で)に格納されています.

私は他のさまざまな投稿を見てきました。StackOverflow のアナグラムがありますが、この特定の問題に対処しているようには見えません。

これが私がこれまでに持っているものです：

- (BOOL) doesEightLetterWord: (NSString* )haystack containWord: (NSString *)needle {
    for (int i = 0; i < [needle length] + 1; i++) {
        if (!needle) {
            NSLog(@"DONE!");
        }

        NSString *currentCharacter = [needle substringWithRange:NSMakeRange(i, 1)];
        NSCharacterSet *set = [NSCharacterSet characterSetWithCharactersInString: currentCharacter];
        NSLog(@"Current character is %@", currentCharacter);
        if ([haystack rangeOfCharacterFromSet:set].location == NSNotFound) {
            NSLog(@"The letter %@ isn't found in the word %@", currentCharacter,    haystack);
            return FALSE;
        } else {
            NSLog(@"The letter %@ is found in the word %@", currentCharacter, haystack);
            int currentLocation = [haystack rangeOfCharacterFromSet: set].location;
            currentLocation++;    
            NSString *newHaystack = [haystack substringFromIndex: currentLocation];
            NSString *newNeedle = [needle substringFromIndex: i + 1];
            NSLog(@"newHaystack is %@", newHaystack);
            NSLog(@"newNeedle is %@", newNeedle);
        }
    }
}
4

3 に答える 3

1

文字の一部だけを使用する場合、それは真のアナグラムではありません。

あなたの場合の良いアルゴリズムは、ソートされた文字列を取得して文字ごとに比較し、長い単語の不一致をスキップすることです。短い単語の最後に到達した場合は、一致しています。

char *p1 = shorter_word;
char *p2 = longer_word;
int match = TRUE;
for (;*p1; p1++) {
  while (*p2 && (*p2 != *p1)) {
    p2++;
  }
  if (!*p2) {
    /* Letters of shorter word are not contained in longer word */
    match = FALSE;
  }
}
于 2012-11-14T14:17:43.837 に答える
0

これは、ある順序付けられた単語に別の順序付けられた単語のすべての文字が含まれているかどうかを調べるためのアプローチの 1 つです。真のアナグラムは見つからないことに注意してください（2つの順序付けられた文字列が同じである必要があるだけです）が、これはあなたが求めていると思います：

+(BOOL) does: (NSString* )longWord contain: (NSString *)shortWord {
    NSString *haystack = [longWord copy];
    NSString *needle = [shortWord copy];
    while([haystack length] > 0 && [needle length] > 0) {
        NSCharacterSet *set = [NSCharacterSet characterSetWithCharactersInString: [needle substringToIndex:1]];
        if ([haystack rangeOfCharacterFromSet:set].location == NSNotFound) {
            return NO;
        }
        haystack = [haystack substringFromIndex: [haystack rangeOfCharacterFromSet: set].location+1];
        needle = [needle substringFromIndex: 1];
    }

    return YES;
}
于 2012-11-14T14:24:02.183 に答える
0

最も簡単な (ただし最も効率的ではない) 方法は、 を使用することNSCountedSetです。これを行うことができるのは、カウントされたセットの場合、 for every inの[a isSubsetOfSet:b]場合にのみ YES を返すためです。[a countForObject:object] <= [b countForObject:object]objecta

それを行うためにカテゴリを追加しましょうNSString:

@interface NSString (lukech_superset)

- (BOOL)lukech_isSupersetOfString:(NSString *)needle;

@end

@implementation NSString (lukech_superset)

- (NSCountedSet *)lukech_countedSetOfCharacters {
    NSCountedSet *set = [NSCountedSet set];
    [self enumerateSubstringsInRange:NSMakeRange(0, self.length) options:NSStringEnumerationByComposedCharacterSequences usingBlock:^(NSString *substring, NSRange substringRange, NSRange enclosingRange, BOOL *stop) {
        [set addObject:substring];
    }];
    return set;
}

- (BOOL)lukech_isSupersetOfString:(NSString *)needle {
    return [[needle lukech_countedSetOfCharacters] isSubsetOfSet:[self lukech_countedSetOfCharacters]];
}

@end
于 2012-11-14T19:41:52.510 に答える