在编写算法时需要帮助 [英] Need help in writing an algorithm

问题描述

我从Careercup.com得到了这个问题。在微软的采访中被问过。

想象一下，我们有一个大字符串，如ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD，其中包含多个回文，如ABCBA，RACECAR，ARA，IAMAI等...现在写一个方法它将接受这个大字符串并返回该字符串中最大的回文。如果有两个相同大小的回文，只需返回其中任何一个就足够了。

I got this question from Careercup.com. It was asked in a microsoft interview.
Imagine we have a large string like this "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD" which contains multiple palindromes within it, like ABCBA, RACECAR, ARA, IAMAI etc... Now write a method which will accept this large string and return the largest palindrome from this string. If there are two palindromes which are of same size, it would be sufficient to just return any one of them.

推荐答案

通常我不会这样做，但它很有趣:)

Normally I wouldn't do this, but it was kind of fun :)

class Program
{
    static void Main(string[] args)
    {
        List<string> palens = Palendromerize("ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD");

        foreach (string palen in palens)
            Console.WriteLine("Palendrome: " + palen);

        Console.ReadKey();
    }

    static List<string> Palendromerize(string s)
    {
        string reverseStr = new string(s.Reverse().ToArray());

        List<string> retVal = new List<string>();

        for (int i = 0; i < s.Length; i++)
        {
            string s1 = new string(' ', s.Length - i - 1) + s;
            string s2 = new string(' ', i) + reverseStr;

            string matches = string.Empty;
            //Now match between the two...
            for (int x = 0; x < Math.Min(s1.Length, s2.Length); x++)
            {
                if (s1[x] == s2[x])
                    matches += s1[x];
                else
                    matches += ' ';
            }

            string[] palens = matches.Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);

            for (int m = 0; m < palens.Length; m++)
                if (palens[m].Length >= 3)
                    retVal.Add(palens[m]);
        }

        return retVal;
    }
}

输出：

古院：ABCBA

综合征：OHO

综合征：RACECAR

综合征：ARA

综合征：RAR

Palendrome：IAMAI



基本上这是通过沿着另一个字符串滑动每个字符串来工作，只关注匹配的字符串片段。然后，您将获取与两个字符串中的位置匹配的任何字符，并将它们添加到数组中。拆分数组，删除空条目。然后由于综合症的最小长度为3，过滤掉较短的那些，然后将它们添加到结果列表中。

Output:
Palendrome: ABCBA
Palendrome: OHO
Palendrome: RACECAR
Palendrome: ARA
Palendrome: RAR
Palendrome: IAMAI

Basically this works by sliding each string along the other one, only paying attention to the pieces of the string that match up. Then you take any characters that match positions in both strings and add them to an array. Split the array removing empty entries. Then since the minimum length of a palendrome is 3, filter out the ones that are shorter and then add them to the results list.

检查此链接

< a href =http://strivingandlearning.blogspot.in/2013/06/find-longest-palindrome-in-given-string.html> find-longest-palindrome-in-given-string [< a href =http://strivingandlearning.blogspot.in/2013/06/find-longest-palindrome-in-given-string.htmltarget =_ blanktitle =New Window> ^ ]



使用linq尝试这个简单的方法：

check this link
find-longest-palindrome-in-given-string[^]

Try this simple approach using linq:

string input = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
            List<string> allPossibleCombination = new List<string>();
            for (int i = 0; i < input.Length; i++)
                for (int j = 0; j < input.Length; j++)
                    try
                    {
                        allPossibleCombination.Add(input.Substring(i, j));
                    }
                    catch (Exception)
                    {
                        break;
                    }
            var palidroms = allPossibleCombination.Where(k => new string(k.Reverse().ToArray()) == k);
            string max = palidroms.OrderByDescending(k => k.Length).First();
            // output : "RACECAR"

这篇关于在编写算法时需要帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！