[HackerRank] Sherlock and Anagrams

2019-05-22 글쓴이 TED HONG

[HackerRank] Sherlock and Anagrams

문자열내의 Anagram 쌍이 몇개인지 찾는 문제

단어를 잘라서 Lowercase 로 변환, 정렬 후

Dictionary 에  (단어, 갯수) 로 넣어서  계산하는 방식도 될 거 같은데

일단 무식한 방법으로 풀어봤다.

3중for문이라 인풋값에 긴 문자열이 들어오면

타임아웃이 뜬다;;; 

 

static int sherlockAndAnagrams(string s)
        {
            int result = 0;
            for (int i = 1; i < s.Length + 1; i++) //i 는 단어의 길이 점점 늘어남
            {
                List words = new List();
                for (int j = 0; j < s.Length - (i -1); j++)
                {
                    string word = s.Substring(j, i);
                    words.Add(word);
                    Console.WriteLine(j + " , "+ i +" / "+ word);
                }
                Console.WriteLine("words count = "+ words.Count);
                
                for (int k = 0; k < words.Count - 1; k++)
                {
                    for (int l = k + 1; l < words.Count; l++)
                    {
                        if (isAnagram(words[k], words[l]))
                            result++;
                    }
                }
            }

            Console.WriteLine("result = "+result);

            return result;
        }

        static bool isAnagram(string str1, string str2)
        {
            if (str1.Length != str2.Length) return false;

            char[] char1 = str1.ToLower().ToCharArray();
            char[] char2 = str2.ToLower().ToCharArray();

            Array.Sort(char1);
            Array.Sort(char2);

            string nStr1 = new string(char1);
            string nStr2 = new string(char2);
            Console.WriteLine(nStr1 + " / " + nStr2);
            return nStr1.Equals(nStr2);
        }