1

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

例如

“Atom another era” [ atomhas aand tin common withanother和 anotherhas eand ain common with era（答案不是唯一的）。

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

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

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

4

3 回答 3

4

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

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

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

如果假设单词是英语或其他语言中的单词，并且具有最大单词长度，那么恒定时间和线性时间之间的差异是相当没有意义的，因为（为了论证）所有小于最大长度的单词都可以被填充与不匹配的字符，这将导致一个恒定的时间算法。

一旦有了两个单词的位字段，您可以通过将它们组合在一起并检查结果是否不为零（这表示没有共同的字母）而不是 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;
}

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

于 2015-07-16T08:44:23.453 回答
2

第 1 部分：wordOne和wordTwo2 一致吗？

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;
}
于 2015-07-16T07:38:12.147 回答
1

首先，我需要一个数据结构，它需要 2 个单词并在恒定时间内回答“这些单词是否至少有 2 个共同字母？”这个问题。

简单的。首先计算您正在使用的字典的邻接矩阵，其中“相邻”定义为“至少有两个共同字母”。我不同意上面的评论，现在即使存储一本综合的英语词典也不是很多数据。存储完整的邻接矩阵可能会占用您喜欢的太多空间，因此请使用稀疏数组工具。

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

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

于 2015-07-16T07:46:40.147 回答