重新排列Array中的字母并检查排列是否在数组中

Question

我正在制作一个ios应用程序，您在其中输入9个字母并输出这9个字母的字母。它就像是纸上的目标词，或9个字母的单词。像这样的链接：

http://nineletterword.tompaton.com/

它不只是为9个字母提供字谜，它会做它的4个字母，5个字母，6个字母......所有这些都至少包含字母中间。

我想使它成为离线应用程序，所以我不想引用任何网站或使用在线JSON ...

我怎么会去检查，如果9个字母组成的数组可以重新排列成我已经下载的英文词典中的一个单词。

E.g.我输入了（a，b，a，n，D，o，n，e，d）：如何获得4个字母或更多的英文单词输出称为“英语词典”其中必须包含中间字母“D” - 如“放弃”，“债券”，“死”...

是最好的方法很多很多的循环，如果语句或是有东西在xcode/objective c我可以用先手的4个字母列表，然后有它的所有可能的排列...

干杯

Answer 1

让我提出一个不同的算法依赖于一个查询，而不是通过一个数组的搜索。

设置：

迭代字典中的单词。对于每个单词，创建一个具有相同字符的字符串，按字母顺序排序。使用此字符串作为关键字，创建原始单词数组的字典。

用法：

现在你可以做任何字符组合的检查非常快：就像上面的字符排序和查找产生的向上键在地图。

例子：

原始数组：(bond, Mary, army)

字谜查找图：

{ 
    bdno : (bond), 
    amry : (Mary, army), 
} 

使用这种地图是非常快的检查任何字的字谜。不需要迭代字典数组。

编辑：

我提出的算法分割在三个部分：

1. 甲设置方法来构建从对象的字典中查找图：anagramMap
2. 的方法，来计算字符按字符排序的键：anagramKey
3. 一种算法，可查找包含在九个字母单词中的所有字符的排列并查找w地图上的ords：findAnagrams。

这里的所有三种方法作为一个类别的上NSString实现：

@interface NSString (NSStringAnagramAdditions) 
- (NSSet *)findAnagrams; 
@end 

@implementation NSString (NSStringAnagramAdditions) 

+ (NSDictionary *)anagramMap 
{ 
    static NSDictionary *anagramMap; 
    if (anagramMap != nil) 
     return anagramMap; 

    // this file is present on Mac OS and other unix variants 
    NSString *allWords = [NSString stringWithContentsOfFile:@"/usr/share/dict/words" 
                encoding:NSUTF8StringEncoding 
                 error:NULL]; 

    NSMutableDictionary *map = [NSMutableDictionary dictionary]; 
    @autoreleasepool { 
     [allWords enumerateLinesUsingBlock:^(NSString *word, BOOL *stop) { 
      NSString *key = [word anagramKey]; 
      if (key == nil) 
       return; 
      NSMutableArray *keyWords = [map objectForKey:key]; 
      if (keyWords == nil) { 
       keyWords = [NSMutableArray array]; 
       [map setObject:keyWords forKey:key]; 
      } 
      [keyWords addObject:word]; 
     }]; 
    } 

    anagramMap = map; 
    return anagramMap; 
} 

- (NSString *)anagramKey 
{ 
    NSString *lowercaseWord = [self lowercaseString]; 

    // make sure to take the length *after* lowercase. it might change! 
    NSUInteger length = [lowercaseWord length]; 

    // in this case we're only interested in anagrams 4 - 9 characters long 
    if (length < 4 || length > 9) 
     return nil; 

    unichar sortedWord[length]; 
    [lowercaseWord getCharacters:sortedWord range:(NSRange){0, length}]; 

    qsort_b(sortedWord, length, sizeof(unichar), ^int(const void *aPtr, const void *bPtr) { 
     int a = *(const unichar *)aPtr; 
     int b = *(const unichar *)bPtr; 
     return b - a; 
    }); 

    return [NSString stringWithCharacters:sortedWord length:length]; 
} 

- (NSSet *)findAnagrams 
{ 
    unichar nineCharacters[9]; 
    NSString *anagramKey = [self anagramKey]; 

    // make sure this word is not too long/short. 
    if (anagramKey == nil) 
     return nil; 
    [anagramKey getCharacters:nineCharacters range:(NSRange){0, 9}]; 
    NSUInteger middleCharPos = [anagramKey rangeOfString:[self substringWithRange:(NSRange){4, 1}]].location; 

    NSMutableSet *anagrams = [NSMutableSet set]; 

    // 0x1ff means first 9 bits set: one for each character 
    for (NSUInteger i = 0; i <= 0x1ff; i += 1) { 

     // skip permutations that do not contain the middle letter 
     if ((i & (1 << middleCharPos)) == 0) 
      continue; 

     NSUInteger length = 0; 
     unichar permutation[9]; 
     for (int bit = 0; bit <= 9; bit += 1) { 
      if (i & (1 << bit)) { 
       permutation[length] = nineCharacters[bit]; 
       length += 1; 
      } 
     } 

     if (length < 4) 
      continue; 

     NSString *permutationString = [NSString stringWithCharacters:permutation length:length]; 
     NSArray *matchingAnagrams = [[self class] anagramMap][permutationString]; 

     for (NSString *word in matchingAnagrams) 
      [anagrams addObject:word]; 
    } 

    return anagrams; 
} 

@end 

假设在一个名为变量测试字符串nineletters你会使用日志的可能值：

for (NSString *anagram in [nineletters findAnagrams]) 
    NSLog(@"%@", anagram); 

Answer 2

首先，你需要一种方法来检查，如果一个字是第二个字的字谜。有很多可能的解决方案（搜索“Objective-C anagram”）。这实质上是从 https://stackoverflow.com/a/13465672/1187415的方法，书面略有不同：

- (BOOL)does:(NSString*)longWord contain:(NSString *)shortWord 
{ 
    NSMutableString *longer = [longWord mutableCopy]; 
    __block BOOL retVal = YES; 
    // Loop over all characters (letters) in shortWord: 
    [shortWord enumerateSubstringsInRange:NSMakeRange(0, [shortWord length]) 
            options:NSStringEnumerationByComposedCharacterSequences 
           usingBlock:^(NSString *substring, NSRange substringRange, NSRange enclosingRange, BOOL *stop) { 
     // Check if letter occurs in longer word: 
     NSRange letterRange = [longer rangeOfString:substring]; 
     if (letterRange.location != NSNotFound) { 
      // Yes. Remove from longer word and continue. 
      [longer deleteCharactersInRange:letterRange]; 
     } else { 
      // No. Set return value to NO and quit the loop. 
      retVal = NO; 
      *stop = YES; 
     } 
    }]; 
    return retVal; 
} 

例子：

• [self does:@"abandoned" contain:@"bond"] = YES
• [self does:@"abandoned" contain:@"sea"] = NO，因为没有 “S” 的第一个字。
• [self does:@"abandoned" contain:@"noon"] = NO，因为“中午”有2个字母“o”，但 第一个字只有一个“o”。

然后你就可以进行如下操作：

NSArray *englishWords = ...; // Your array of english words 

NSString *inputWord = @"abandoned"; // The input string 
NSString *middleLetter = [inputWord substringWithRange:NSMakeRange([inputWord length]/2, 1)]; 

NSPredicate *predicate = [NSPredicate predicateWithBlock:^BOOL(NSString *word, NSDictionary *bindings) { 
    // Word must have at least 4 letters: 
    if ([word length] < 4) 
     return NO; 
    // Word must contain the middle letter: 
    if ([word rangeOfString:middleLetter].location == NSNotFound) 
     return NO; 
    // Word must contain only letters of the input word: 
    if (![self does:inputWord contain:word]) 
     return NO; 
    return YES; 
}]; 
NSArray *matchingWords = [englishWords filteredArrayUsingPredicate:predicate]; 
NSLog(@"%@", matchingWords);