至少有2个常用字母的单词

Question

如果每个单词至少有 2 个字母与下一个单词相同，则字符串被命名为 2-consistent。

例如

"Atom another era" [atom has a and t in common with another and another has e and a in common with era (the answer is not unique).

首先，我需要一个数据结构，它需要 2 个单词并在固定时间内回答问题 "Do these words have at least 2 letters in common?"

现在，给定一串 n 个单词，我需要找到 最长的 2-consistent 子字符串。

我不知道要使用什么数据结构。我想 radix tree 或 prefix tree，但找不到答案。你能帮帮我吗？

Answer 1

第 1 部分：wordOne 和 wordTwo 是 2 一致的吗？

public bool IsWordsTwoConsistent(string first, string second)
{
    int[] letters = Enumerable.Repeat(0, 26).ToArray();
    int countDoubles = 0;

    foreach (char c in first.toLowerCase())
    {
        letters[(int)c - 97]++;
    }

    foreach (char c in second.toLowerCase())
    {
        if (letters[(int)c - 97] > 0)
            countDoubles++;

        if (countDoubles > 1)
            return true;
    }

    return false;
}

第 2 部分：最长 2 一致子串

public int GetPositionLongestTwoConsistentSubstring(string input)
{
    string[] wordsArray = input.Split(' ');
    int maxLocation = -1, maxLength = 0;
    int candLocation = -1, candLength = 0;  //candiadate

    for (int i = 0 ; i < wordsArray.Length - 1 ; i++)
    {
        if (IsWordsTwoConsistent(wordsArray[i], wordsArray[i+1]))
        {
            candLength++;
            if (candLocation == -1)
                candLength = i;
        }
        else
        {
            if (candLength > maxLength)
            {
                maxLength = candLength;
                maxLocation = candLocation;
            }           
            candLength = 0;
            candLocation = -1;
        }
    }

    if (candLength > maxLength)
    {
        maxLength = candLength;
        maxLocation = candLocation;
    }

    return maxLocation;
}

Answer 2

First of all I need a data structure which takes 2 words and answers in constant time at the question "Do these words have at least 2 letters in common?"

简单。首先计算您正在使用的词典的邻接矩阵，其中 'adjacent' 定义为 'having at least two letters in common'。我不同意上面的评论，这些天存储即使是综合英语词典也不是很多数据。根据您的喜好，存储完整的邻接矩阵可能需要太多 space，因此请使用稀疏数组工具。

现在，请记住，英语单词只是一个 base-26 的数字（如果您坚持区分大写字母，则为 base-52），因此查找一对单词的行和列是一个常量-时间操作，你的问题就有了答案。

哦，当然，这会消耗 space 并进行大量的预计算，但 OP 会询问用于在恒定时间内回答问题的数据结构。

Answer 3

假设没有重音字母并忽略大写，对于每个单词，您可以在 32 位整数中存储一个位域，如果存在来自 a-z 的对应字母，则位 0-25 设置为 1。

可以像这样在线性时间内计算整数：

int getBitField(char* word)
{
    int bits = 0;
    while(*word)
        bits |= 1 << ((*word++) - 'a');
    return bits;
}

如果假定单词是英语或其他语言的单词，并具有最大单词长度，那么常数时间和线性时间之间的差异就毫无意义，因为（为了论证）所有单词都小于最大长度length 可以用不匹配的字符填充，这将导致恒定时间算法。

一旦你有了两个单词的位字段，你就可以测试它们在常数时间内是否是 2 一致的，方法是将它们与在一起并检查结果是否不为零（这表明没有共同的字母）而不是一个2 的幂（表示只有一个字母是共同的，因为只设置了一个位）。您可以通过对一个数字本身减 1 进行与运算来测试 2 的幂。

bool is2Consistent(int word1bits, int word2bits)
{
    int common = word1bits & word2bits;
    return (common & (common - 1)) != 0;
}

如果您打算定义像 'meet' 和 'beef' 这样重复字母为 2-consistent 的单词，这将不起作用。

如果你想测试3-consistency，你只需要在函数中多加一行：

bool is3Consistent(int word1bits, int word2bits)
{
    int common = word1bits & word2bits;
    common &= (common - 1);
    return (common & (common - 1)) != 0;
}

AND 一个整数与自身减一只会删除最低有效位，因此您可以任意多次应用它来测试 4 一致性、5 一致性等。

至少有2个常用字母的单词

Words with at least 2 common letters

algorithm

data-structures

radix-tree