C# - Разделить полностью заглавную строку на отдельные слова (без пробелов)
В настоящее время я работаю над проектом, где мне нужно будет отделить отдельные слова от строки. Подвох в том, что все слова в строке написаны заглавными буквами и не имеют пробелов. Ниже приведен пример вида ввода, который получает программа:
"COMPUTERFIVECODECOLOR"
Это должно быть разделено на следующий результат:
"КОМПЬЮТЕР" "ПЯТЬ" "КОД" "ЦВЕТ"
До сих пор я использовал следующий метод для разделения моих строк (и он работал для всех сценариев, кроме этого крайнего случая):
private static List<string> NormalizeSections(List<string> wordList)
{
var modifiedList = new List<string>();
foreach (var word in wordList)
{
int index = wordList.IndexOf(word);
var split = Regex.Split(word, @"(\p{Lu}\p{Ll}+)").ToList();
split.RemoveAll(i => i == "");
modifiedList.AddRange(split);
}
return modifiedList;
}
Если у кого-то есть какие-либо идеи о том, как с этим справиться, я был бы более чем рад их услышать. Также, пожалуйста, дайте мне знать, если я могу предоставить дополнительную информацию.
2 ответа
Я делаю некоторые предположения о том, как вы хотите найти подходящие слова. Во-первых, при заданном символьном индексе предпочтение будет отдаваться самому длинному подходящему слову в словаре. Во-вторых, если по данному индексу символов не найдено ни одного слова, мы переходим к следующему символу и снова ищем.
Реализация ниже использует Trie для индексации словаря всех допустимых слов. Вместо того, чтобы перебирать каждое слово в словаре, мы затем перемещаемся по каждому символу во входной строке, ища самое длинное слово.
Я поднял реализацию Trie в C# из этого очень удобного ответа SO: /questions/42572861/kak-najti-slovo-iz-massivov-simvolov/42572872#42572872
Редактировать: исправлена ошибка в Trie при добавлении слова, которое является подстрокой существующего слова, например, Emergency, а затем Emerge.
Код доступен на DotNetFiddle.
using System;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
var words = new[] { "COMPUTE", "FIVE", "CODE", "COLOR", "PUT", "EMERGENCY", "MERGE", "EMERGE" };
var trie = new Trie(words);
var input = "COMPUTEEMERGEFIVECODECOLOR";
for (var charIndex = 0; charIndex < input.Length; charIndex++)
{
var longestWord = FindLongestWord(trie.Root, input, charIndex);
if (longestWord == null)
{
Console.WriteLine("No word found at char index {0}", charIndex);
}
else
{
Console.WriteLine("Found {0} at char index {1}", longestWord, charIndex);
charIndex += longestWord.Length - 1;
}
}
}
static private string FindLongestWord(Trie.Node node, string input, int charIndex)
{
var character = char.ToUpper(input[charIndex]);
string longestWord = null;
foreach (var edge in node.Edges)
{
if (edge.Key.ToChar() == character)
{
var foundWord = edge.Value.Word;
if (!edge.Value.IsTerminal)
{
var longerWord = FindLongestWord(edge.Value, input, charIndex + 1);
if (longerWord != null) foundWord = longerWord;
}
if (foundWord != null && (longestWord == null || edge.Value.Word.Length > longestWord.Length))
{
longestWord = foundWord;
}
}
}
return longestWord;
}
}
//Trie taken from: https://stackru.com/a/6073004
public struct Letter
{
public const string Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static implicit operator Letter(char c)
{
return new Letter() { Index = Chars.IndexOf(c) };
}
public int Index;
public char ToChar()
{
return Chars[Index];
}
public override string ToString()
{
return Chars[Index].ToString();
}
}
public class Trie
{
public class Node
{
public string Word;
public bool IsTerminal { get { return Edges.Count == 0 && Word != null; } }
public Dictionary<Letter, Node> Edges = new Dictionary<Letter, Node>();
}
public Node Root = new Node();
public Trie(string[] words)
{
for (int w = 0; w < words.Length; w++)
{
var word = words[w];
var node = Root;
for (int len = 1; len <= word.Length; len++)
{
var letter = word[len - 1];
Node next;
if (!node.Edges.TryGetValue(letter, out next))
{
next = new Node();
node.Edges.Add(letter, next);
}
if (len == word.Length)
{
next.Word = word;
}
node = next;
}
}
}
}
Выход:
Found COMPUTE at char index 0
Found EMERGE at char index 7
Found FIVE at char index 13
Found CODE at char index 17
Found COLOR at char index 21
Предполагая, что слова в словаре не содержат друг друга (например, "TOO" и "TOOK"), я не понимаю, почему эта проблема требует более сложного решения, чем эта однострочная функция:
static public List<string> Normalize(string input, List<string> dictionary)
{
return dictionary.Where(a => input.Contains(a)).ToList();
}
(Если слова содержат друг друга, см. Ниже.)
Полный пример:
using System;
using System.Linq;
using System.Collections.Generic;
public class Program
{
static public List<string> Normalize(string input, List<string> dictionary)
{
return dictionary.Where(a => input.Contains(a)).ToList();
}
public static void Main()
{
List<string> dictionary = new List<string>
{
"COMPUTER","FIVE","CODE","COLOR","FOO"
};
string input = "COMPUTERFIVECODECOLORBAR";
var normalized = Normalize(input, dictionary);
foreach (var s in normalized)
{
Console.WriteLine(s);
}
}
}
Выход:
COMPUTER
FIVE
CODE
COLOR
С другой стороны, если вы определили, что ваши ключевые слова действительно перекрываются, вам не повезло. Если вы уверены, что входная строка содержит только слова, которые есть в словаре, и что они являются случайными, вы можете использовать более сложную функцию.
static public List<string> Normalize2(string input, List<string> dictionary)
{
var sorted = dictionary.OrderByDescending( a => a.Length).ToList();
var results = new List<string>();
bool found = false;
do
{
found = false;
foreach (var s in sorted)
{
if (input.StartsWith(s))
{
found = true;
results.Add(s);
input = input.Substring(s.Length);
break;
}
}
}
while (input != "" && found);
return results;
}
public static void Main()
{
List<string> dictionary = new List<string>
{
"SHORT","LONG","LONGER","FOO","FOOD"
};
string input = "FOODSHORTLONGERFOO";
var normalized = Normalize2(input, dictionary);
foreach (var s in normalized)
{
Console.WriteLine(s);
}
}
Это работает так, что он смотрит только на начало строки и сначала ищет самые длинные ключевые слова. Когда он найден, он удаляет его из входной строки и продолжает поиск.
Выход:
FOOD
SHORT
LONGER
FOO
Обратите внимание, что "LONG" не включен, потому что мы включили "LONGER", но "FOO" включен, потому что он находится в строке, отдельной от "FOOD".
Кроме того, в этом втором решении ключевые слова будут отображаться в словаре результатов в том же порядке, в котором они были в исходной строке. Поэтому, если требовалось на самом деле разделить фразу, а не просто определять ключевые слова в любом порядке, вам следует использовать вторую функцию.