我正在制作一个 ios 应用程序，您可以在其中输入 9 个字母，它会输出这 9 个字母的变位词。它就像论文中的目标词或 9 个字母的词。喜欢这个链接:

http://nineletterword.tompaton.com/

它不仅提供 9 个字母的字谜，它还会提供 4 个字母、5 个字母、6 个字母……所有这些字母都至少包含中间字母。

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

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

例如我有 (a,b,a,n,D,o,n,e,d) 的输入:我如何获得数组中 4 个或更多字母的英语单词的输出称为“英语词典”，其中必须包含中间字母“D” - 如“abandon”、“bond”、“dead”...

最好的方法是大量的循环和 if 语句，还是 xcode/objective c 中有什么我可以用来获取 4 个字母的列表，然后对它进行所有可能的排列...

干杯

最佳答案

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

设置:

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

用法:

现在您可以非常快速地对任何字符组合进行检查:只需像上面那样对字符进行排序，然后在映射中查找结果键。

例子:

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

字谜查找图:

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

使用此 map 可以非常快速地检查任何单词的字谜。不需要对字典数组进行迭代。

编辑:

我提出的算法分为三个部分:

1. 从对象字典构建查找映射的设置方法:anagramMap
2. 逐字符排序key的计算方法:anagramKey
3. 找到九个字母单词中包含的字符的所有排列并在映射中查找单词的算法: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);

关于ios - 重新排列数组中的字母并检查排列是否在数组中，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15859238/