包含至少2个普通字母的单词

Question

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

---

例如

"原子另一个时代"[atom有a和t与another和another有e和a与era相同(答案不是唯一的)。

首先，我需要一个数据结构，它在常数时间内接收问题"Do these words have at least 2 letters in common?"的两个单词和答案

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

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

Answer 1

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

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

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

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

一旦你有了两个单词的位域，你可以通过将它们放在一起并检查结果是否为零(这表明没有共同的字母)并且不是2的幂(这将表明只有一个共同的字母，因为只有一个位设置)来测试它们是否在常数时间内是2一致的。你可以用一个数和它本身减去1来测试2的幂。

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

如果你想把像'meet'和'beef'这样有重复字母的词定义为2-consistent，这是行不通的。

如果你想测试3-一致性，你只需要在函数中添加额外的一行:

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

用一个整数本身减去1只会去掉最低有效位，所以你可以应用它任意次数来测试4-一致性，5-一致性等

Answer 2

第一部分:wordOne和wordTwo是否一致?

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 3

首先，我需要一个数据结构，它需要2个单词和答案在固定时间内回答"这些单词是否至少有2个?共同的字母?"

容易。首先计算你正在使用的字典的邻接矩阵，其中"邻接"被定义为"至少有两个相同的字母"。我不同意上面的评论，现在即使存储一本全面的英语词典也不是很多数据。存储完整的邻接矩阵可能会占用您喜欢的太多空间，因此使用稀疏数组设施。

现在，请记住，英语单词只是一个以26为基数的数字(或以52为基数的数字，如果你坚持要区分大写字母)，所以在行和列中查找一对单词是一个常量时间操作，你就有了问题的解决方案。

哦，当然，这会消耗空间并需要相当数量的预计算，但是OP要求在常数时间内回答问题的数据结构