寻找Objective-C变位词的算法

Question

我有一个算法可以在一组八个字母的单词中查找变位词。实际上，它是将较长单词中的字母按字母顺序排序，然后依次对短单词进行相同的操作，并查看它们是否存在于较长单词中，就像这样： = = = 这里的问题是，如果我在 (或tower中)查找，它会找到，没有问题。Rot被发现在tower中。然而，由于中间的R，不在 (或two在tower中)中。因此，它认为two没有出现在tower中。

有更好的方法吗？我正在尝试在Objective-C中完成它，八个字母的单词和常规单词都存储在中（与它们的正常和按字母顺序排序后的形式）。

我已经查看了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);
        }
    }
}

- Luke

---

从（有序的）“haystack”中删除直到并包括“needle”的第一个字符的所有字母。重复此操作，直到其中一个单词为空。 - Edd

对不起，我不太明白针和干草堆的比喻。你能再具体解释一下吗？ - Luke

抱歉，我现在没有时间给出具体的例子，但是“haystack”是你要查找的单词（比如说“eortw”），而“needle”则是你要查找的术语（实际上每次只需要查找第一个字母，但是假设这个字母组合是“otw”或“ort”）。 - Edd

好的，我觉得这很有道理，我肯定可以试一试。如果您以后有更多信息，我会非常感激，但是谢谢您，这应该可以工作！ - Luke

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

- Klas Lindbäck

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

- Edd

---

看起来不错。现在要查看stringAfterIndex或getFirstIndex在任何形式下是否存在于Objective-C中。 - Luke

@lukech 我认为你可以使用 substringFromIndex: 和 rangeOfCharacterFromSet:。 - Edd

substringFromIndex:会起作用，但我需要一种获取该子字符串第一个实例的方法。我已经修改添加了上面的方法。 - Luke

还有，你在那里返回一个方法调用吗？ - Luke

@lukech 我已经更新了答案，提供了一个使用迭代方法的实际 Objective-c 方法。我认为你问题中的版本存在的问题是你从未更新 haystack 或 needle - 你只是将值分配给了 newHaystack 和 newNeedle（这是我在之前的示例中使用的方便变量，旨在使递归更清晰）。 - Edd

Answer 3

最简单（但不是最有效）的方法可能是使用NSCountedSet。我们可以这样做，因为对于计数集，[a isSubsetOfSet:b]仅当每个object在a中时，[a countForObject:object] <= [b countForObject:object]返回YES。

让我们添加一个类别到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

- rob mayoff