雅虎公司C#笔试题(后半部份才是)

“雅虎公司C#笔试题(后半部份才是)”是一道常见于程序员面试和笔试的题目。下面就从如何解题的角度，为大家讲解完整攻略。

题目描述

题目大意是给出两个字符串，求它们在其中一个字符串中的最长公共子串。

具体需要完成的是，实现一个方法 string Find(string str1, string str2, string source)，其中：

1. 参数 str1 和 str2 分别表示两个字符串，字符串长度小于 100。
2. 参数 source 表示包括 str1 和 str2 的字符串，字符串长度小于 1000。
3. 返回值为 str1 和 str2 在 source 中的最长公共子串，如果不存在，返回空字符串。

解题思路

本题要求的是两个字符串在另一个字符串中的最长公共子串，因此我们可以采用一种类似于动态规划的思路来解决。

首先定义一个二维数组 dp，其中 dp[i,j] 表示以 source[i-1] 和 source[j-1] 结尾的两个子串的最长公共子串长度。这里用 i-1 和 j-1 是为了避免数组越界问题。

然后我们重复执行以下步骤，直到所有的 dp 值都求出来：

1. 如果 source[i-1] == source[j-1]，那么 dp[i,j] 就等于 dp[i-1,j-1] + 1。
2. 否则，dp[i,j] 就等于 0。

我们再定义两个变量 maxLen 和 endIndex，分别表示最长公共子串的长度和结束位置。我们在更新每个 dp[i,j] 的时候，如果它的值比 maxLen 还大，就更新 maxLen 和 endIndex。

最后，我们从 endIndex-maxLen 的位置开始，取出长度为 maxLen 的子串，就是我们要求的最长公共子串。

代码实现

下面是 C# 语言的完整代码实现。

public string Find(string str1, string str2, string source)
{
    if (string.IsNullOrEmpty(str1) || string.IsNullOrEmpty(str2) || string.IsNullOrEmpty(source))
    {
        return string.Empty;
    }

    int len1 = str1.Length;
    int len2 = str2.Length;
    int len = source.Length;
    int maxLen = 0;
    int endIndex = 0;

    int[,] dp = new int[len + 1, len + 1];

    for (int i = 1; i <= len; i++)
    {
        for (int j = 1; j <= len; j++)
        {
            if (source[i - 1] == str1[j - 1])
            {
                dp[i, j] = dp[i - 1, j - 1] + 1;
                if (dp[i, j] > maxLen)
                {
                    maxLen = dp[i, j];
                    endIndex = i;
                }
            }
        }
    }

    if (maxLen == 0)
    {
        return string.Empty;
    }

    return source.Substring(endIndex - maxLen, maxLen);
}

示例说明

为了更好地理解上述代码，我们来看两个示例。

示例一

假设给定的输入是：

str1: "hello"
str2: "world"
source: "helloworld"

执行 Find 方法后，我们得到的输出应该是 "world"。

这是因为 "world" 是字符串 "hello" 和 "world" 在字符串 "helloworld" 中的最长公共子串。

示例二

假设给定的输入是：

str1: "abcd"
str2: "efgh"
source: "ijkl"

执行 Find 方法后，我们得到的输出应该是空字符串 ""。

这是因为字符串 "abcd" 和 "efgh" 在字符串 "ijkl" 中不存在公共子串。