TCHS08 Online Round 3 Easy 練習

問題

同じ文字の出現回数で文字列の類似度をはかります。文字列がたくさん与えられるので、一番類似度の高い文字列のペアの類似度を求めなさい。

解

やるだけなんだけど、これがもっと早く書けるといいな。

類似度計算が汚い。ヒストグラム使うとかスマートな方法が使えたらよかった。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class SimilarWords {
    private int sim(List<char> a, List<char> b)
    {
        int i = 0, res = 0;

        while (i < a.Count)
        {
            int pos = b.IndexOf(a[i]);
            if (pos != -1)
            {
                b.RemoveAt(pos);
                res++;
            }
            i++;
        }
        return res;
    }

    public int mostSimilarPair(string[] words) {
        for (int i = 0; i < words.Length; ++i)
        {
            char[] t = words[i].ToLower().ToCharArray();
            Array.Sort(t);
            words[i] = new string(t);
        }

        int maxs = 0;
        for (int i = 0; i < words.Length; i++)
        {
            for (int j = i + 1; j < words.Length; ++j)
            {
                string a = words[i].Length < words[j].Length ? words[i] : words[j];
                string b = words[i].Length < words[j].Length ? words[j] : words[i];
                maxs = Math.Max(maxs, sim(new List<char>(a.ToCharArray()), new List<char>(b.ToCharArray())));
            }
        }
        return maxs;
    }
}