重新排列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);