3

Есть список:

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);

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

9
  • А чем текущий способ не устраивает? Вроде все лаконично и самое главное, что работает
    – iluxa1810
    20 апр 2017 в 18:39
  • 1
    @iluxa1810 - нет, код не работает. Добавьте в начало списка "строка1","строка3","строка4". Ошибка классическая - удаление из списка внутри цикла по нему.
    – user176262
    20 апр 2017 в 18:42
  • Новый вариант стоит добавлять в конец вопроса, а не заменять им первоначальный.
    – Regent
    20 апр 2017 в 18:51
  • @Igor, завернул еще в один цикл.
    – tretetex
    20 апр 2017 в 18:51
  • @Skrim - опять мимо: removedCount += ... внутри for и removedCount = 0; перед for
    – user176262
    20 апр 2017 в 18:51

2 ответа 2

3

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

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

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;
    }
}
3
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--;
    }
  }
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.