Получить уникальные значения списка

210

21 апреля 2017, 17:36

Есть список:

var list = new List<string> {
    "строка",
    "строка22у", 
    "строкайцвцйй", 
    "текстцвцй", 
    "текст", 
    "текстыауке5"};

Нужно удалить элементы, которые содержат в себе другие элементы. Т.е. удалить строки строка22у, строкайцвцйй, т.к. содержат первую строку и текстцвцй, текстыауке5 соответственно. В результате останутся строка, текст.

Делаю так:

int removedCount;
do
{
    removedCount = 0;
    for (int i = 0; i < list.Count; i++)
    {
        removedCount += list.RemoveAll(x => x.Contains(list[i]) && x != list[i]);
    }
} while (removedCount != 0);

Есть ли более эффективный способ?

Answer 1

При большом количество строк (особенно если многие из них имеют одинаковые префиксы) вариант с построением префиксного дерева и поиску по нему должен работать гораздо быстрее. Однако и кода выходит гораздо больше.

Вариант реализации. Метод поиска требуемых строк:

private static List<string> dfa(List<string> list)
{
    var result = new List<string>();
    State root = new State();
    foreach (string word in list)
    {
        State state = root;
        foreach (char c in word)
        {
            state = state.get(c);
        }
        state.isFinal = true;
    }
    foreach (string word in list)
    {
        State state = root;
        int i = 0;
        for (; !state.isFinal && i < word.Length; i++)
        {
            state = state.get(word[i]);
        }
        if (i == word.Length)
        {
            result.Add(word);
        }
    }
    return result;
}

Вспомогательный класс состояния ДКА с учетом оптимизации:

private class State
{
    private Dictionary<char, State> transitions;
    public bool isFinal = false;
    private char firstChar;
    private State firstState = null;
    public State get(char c)
    {
        if (firstState != null && firstChar == c)
        {
            return firstState;
        }
        if (firstState == null)
        {
            firstState = new State();
            firstChar = c;
            return firstState;
        }
        if (transitions == null)
        {
            transitions = new Dictionary<char, State>();
        }
        if (transitions.ContainsKey(c))
        {
            return transitions[c];
        }
        State state = new State();
        transitions.Add(c, state);
        return state;
    }
}

Answer 2

for (int i = 0; i < list.Count; i++)
{
  for (int j = list.Count - 1; j >= 0; j--)
  {
    if (list[j].Contains(list[i]) && list[i] != list[j])
    {
      list.RemoveAt(j);
      if (j < i)
        i--;
    }
  }
}