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

我正在做一个ios应用程序，你input9个字母，它会输出9个字母的字母。 它就像是目标词，或者是纸上的9个字母词。 喜欢这个链接：

http://nineletterword.tompaton.com/

它不只是提供9个字母的字母，它将为4个字母，5个字母，6个字母…所有这些都至less包含中间字母。

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

我将如何去检查这9个字母的数组是否可以重新排列成一个我已经下载的英文字典中的一个单词。

例如，我有（a，b，a，n， D ，o，n，e，d）的input：如何在一个名为“English Dictionary”的数组中获得4个或更多英文单词的输出必须包含中间字母“D” – 像“放弃”，“债券”，“死”…

是最好的方法很多很多循环，如果语句或是有什么在xcode /目标c我可以用来得到4个字母的列表，然后有所有可能的安排…

干杯

让我提出一个不同的algorithm，它依赖于查找，而不是通过数组search。

build立：

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

用法：

现在，您可以快速地对任何字符组合进行检查：只需对上面的字符进行sorting，然后在地图中查看结果键。

例：

原始排列:( ( bond, Mary, army )

字谜查找地图： 

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

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

编辑：

我提出的algorithm分为三部分：

  1. 从对象字典中构build查找映射的设置方法： anagramMap
  2. 计算逐字符sorting键的方法： anagramKey
  3. 查找包含在九个字母单词中的字符的所有排列并查找映射中的单词的algorithm： 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的variables中有一个testingstring，您可以使用以下方式logging可能的值： 

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

首先你需要一个方法来检查一个单词是否是第二个单词的一个字母。 有很多可能的解决scheme（search“Objective-C anagram”）。 这实质上是https://stackoverflow.com/a/13465672/1187415中的方法，写法略有不同&#xFF1A; 

 - (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 ，因为“noon”有两个字母“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);
Interesting Posts