2.5.2

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

将字符串数组 keywords 按照长度排序,于是 keywords[0] 就是最短的字符串。
组合词的最短长度 minLength = 最短字符串的长度 * 2 = keywords[0] * 2
先找到第一个长度大于等于 minLength 的字符串,下标为 canCombine
我们从 canCombine 开始,一个个检查是否是组合词。
如果 keywords[canCombine] 是一个组合词,那么它一定是由位于它之前的某两个字符串组合而成的。
组合词的长度一定等于被组合词的长度之和,因此我们可以通过长度快速判断有可能的组合词。
现在题目转化为了如何解决 ThreeSum 问题,即求 a + b = c 型问题,根据 1.4.41 中的解法求解。
keywords[canCombine] 的长度已知,i 从 0 到 canCombine 之间循环,
用二分查找确认 icanCombine 之间有没有符合条件的字符串,注意多个字符串可能长度相等。

代码

using System;
using System.Collections.Generic;

namespace _2._5._2
{
    /*
     * 2.5.2
     * 
     * 编写一段程序,从标准输入读入一列单词并打印出其中所有由两个单词组成的组合词。
     * 例如,如果输入的单词为 after、thought 和 afterthought,
     * 那么 afterthought 就是一个组合词。
     * 
     */
    class Program
    {
        /// <summary>
        /// 根据字符串长度进行比较。
        /// </summary>
        class StringLengthComparer : IComparer<string>
        {
            public int Compare(string x, string y)
            {
                return x.Length.CompareTo(y.Length);
            }
        }

        /// <summary>
        /// 二分查找,返回符合条件的最小下标。
        /// </summary>
        /// <param name="keys">搜索范围。</param>
        /// <param name="length">搜索目标。</param>
        /// <param name="lo">起始下标。</param>
        /// <param name="hi">终止下标。</param>
        /// <returns></returns>
        static int BinarySearch(string[] keys, int length, int lo, int hi)
        {
            while (lo <= hi)
            {
                int mid = lo + (hi - lo) / 2;
                if (keys[mid].Length == length)
                {
                    while (mid >= lo && keys[mid].Length == length)
                        mid--;
                    return mid + 1;
                }
                else if (length > keys[mid].Length)
                    lo = mid + 1;
                else
                    hi = mid - 1;
            }
            return -1;
        }

        static void Main(string[] args)
        {
            string[] keywords = Console.ReadLine().Split(' ');
            Array.Sort(keywords, new StringLengthComparer());
            int minLength = keywords[0].Length * 2;
            // 找到第一个大于 minLength 的字符串
            int canCombine = 0;
            while (keywords[canCombine].Length < minLength &&
                canCombine < keywords.Length)
                canCombine++;

            // 依次测试是否可能
            while (canCombine < keywords.Length)
            {
                int sum = keywords[canCombine].Length;
                for (int i = 0; i < canCombine; i++)
                {
                    int start = BinarySearch(keywords, sum - keywords[i].Length, i, canCombine);
                    if (start != -1)
                    {
                        while (keywords[start].Length + keywords[i].Length == sum)
                        {
                            if (keywords[start] + keywords[i] == keywords[canCombine])
                                Console.WriteLine(keywords[canCombine] + " = " + keywords[start] + " + " + keywords[i]);
                            else if (keywords[i] + keywords[start] == keywords[canCombine])
                                Console.WriteLine(keywords[canCombine] + " = " + keywords[i] + " + " + keywords[start]);
                            start++;
                        }                   
                    }
                }
                canCombine++;
            }
        }
    }
}
上一题 下一题