using System;

using System.Collections.Generic;

public class Program

{

    public class Company {

        public string Nome { get; set; }

    }

    public static void Main()

    {

        List<Company> companies = new() {

            new Company { Nome = "The Boeing Company" },

            new Company { Nome = "Airbus" },

            new Company { Nome = "Apple, Inc." },

            new Company { Nome = "Google LLC" },

        };

        string newCompany = "Apple".ToLower();

        var threshold = 0.25f;

        var min = 1.0f;

        var nome = string.Empty;

        var buscas = newCompany.Split(' ');

        foreach (var item in companies) {

            var parts = item.Nome.Split(' ');

            var total = 0.0f;

            var i = 0;

            foreach (var part in parts) {

                if (part.Length <= 3) continue;

                i++;

                var currPart = 1.0f;

                foreach(var busca in buscas) {

                    var curr = LevenshteinDistancia(busca, part.ToLower());

                    Console.Write($"Calculada: {curr} / Última: {currPart} - ParteBusca: {busca} / ParteBanco: {part} | ");

                    if (currPart > curr) currPart = curr;

                }

                Console.WriteLine();

                total += currPart * (part.Length / (float)item.Nome.Length);

                Console.WriteLine($"Ponderada: {total}");

            }

            if (i == 0) i = 1;

            total /= i;

            Console.WriteLine($"Calculada: {total}");

            Console.WriteLine();

            if (min > total) {

                min = total;

                nome = item.Nome;

            }

​

        }

        Console.WriteLine($"{min} {(min <= threshold ? nome : "Nenhum")}");

    }

    public static float LevenshteinDistancia(string source, string target) {

        if (string.IsNullOrEmpty(source)) return string.IsNullOrEmpty(target) ? 0.0f : 1.0f;

        if (string.IsNullOrEmpty(target)) return 1.0f;

        // Inicialização

        int s = source.Length;

        int t = target.Length;

        int[,] d = new int[s + 1, t + 1];

        for (int i = 0; i <= s; i++) d[i, 0] = i;

        for (int j = 0; j <= t; j++) d[0, j] = j;

​

        // Cálculo

        for (int i = 1; i <= s; i++) {

            for (int j = 1; j <= t; j++) {

                int custo = target[j - 1] == source[i - 1] ? 0 : 1; // Tem edição?

                d[i, j] = Math.Min(Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + custo);

            }

        }

        return d[s, t] / (float)s;

    }

}