objective-c - 查找字谜Objective-C的算法

Question

我有一个算法可以在一组八个字母的单词中找到字谜。它实际上是将较长单词中的字母按字母顺序排列，对较短的单词一个接一个地执行相同的操作，然后查看它们是否存在于较长的单词中，如下所示:

塔 = eortw 两个= otw rot = ort

这里的问题是，如果我在 eortw(或 rot in tower)中寻找 ort，它会找到它，没问题。在塔内发现腐烂物。但是，otw 不在 eortw 中(或塔中的两个)，因为中间有 R。因此，它不认为在塔中发现了两个。

有没有更好的方法可以做到这一点？我试图在 Objective-C 中做到这一点，八个字母的单词和常规单词都存储在 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);
        }
    }
}

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