Word break problem: Difference between revisions
Content deleted Content added
Line 1,727: | Line 1,727: | ||
abcdd: |
abcdd: |
||
did not parse with given words</pre> |
did not parse with given words</pre> |
||
=={{header|Visual Basic .NET}}== |
|||
{{trans|Java}} |
|||
<lang vbnet>Module Module1 |
|||
Structure Node |
|||
Private ReadOnly m_val As String |
|||
Private ReadOnly m_parsed As List(Of String) |
|||
Sub New(initial As String) |
|||
m_val = initial |
|||
m_parsed = New List(Of String) |
|||
End Sub |
|||
Sub New(s As String, p As List(Of String)) |
|||
m_val = s |
|||
m_parsed = p |
|||
End Sub |
|||
Public Function Value() As String |
|||
Return m_val |
|||
End Function |
|||
Public Function Parsed() As List(Of String) |
|||
Return m_parsed |
|||
End Function |
|||
End Structure |
|||
Function WordBreak(s As String, dictionary As List(Of String)) As List(Of List(Of String)) |
|||
Dim matches As New List(Of List(Of String)) |
|||
Dim q As New Queue(Of Node) |
|||
q.Enqueue(New Node(s)) |
|||
While q.Count > 0 |
|||
Dim node = q.Dequeue() |
|||
REM check if fully parsed |
|||
If node.Value.Length = 0 Then |
|||
matches.Add(node.Parsed) |
|||
Else |
|||
For Each word In dictionary |
|||
REM check for match |
|||
If node.Value.StartsWith(word) Then |
|||
Dim valNew = node.Value.Substring(word.Length, node.Value.Length - word.Length) |
|||
Dim parsedNew As New List(Of String) |
|||
parsedNew.AddRange(node.Parsed) |
|||
parsedNew.Add(word) |
|||
q.Enqueue(New Node(valNew, parsedNew)) |
|||
End If |
|||
Next |
|||
End If |
|||
End While |
|||
Return matches |
|||
End Function |
|||
Sub Main() |
|||
Dim dict As New List(Of String) From {"a", "aa", "b", "ab", "aab"} |
|||
For Each testString In {"aab", "aa b"} |
|||
Dim matches = WordBreak(testString, dict) |
|||
Console.WriteLine("String = {0}, Dictionary = {1}. Solutions = {2}", testString, dict, matches.Count) |
|||
For Each match In matches |
|||
Console.WriteLine(" Word Break = [{0}]", String.Join(", ", match)) |
|||
Next |
|||
Console.WriteLine() |
|||
Next |
|||
dict = New List(Of String) From {"abc", "a", "ac", "b", "c", "cb", "d"} |
|||
For Each testString In {"abcd", "abbc", "abcbcd", "acdbc", "abcdd"} |
|||
Dim matches = WordBreak(testString, dict) |
|||
Console.WriteLine("String = {0}, Dictionary = {1}. Solutions = {2}", testString, dict, matches.Count) |
|||
For Each match In matches |
|||
Console.WriteLine(" Word Break = [{0}]", String.Join(", ", match)) |
|||
Next |
|||
Console.WriteLine() |
|||
Next |
|||
End Sub |
|||
End Module</lang> |
|||
{{out}} |
|||
<pre>String = aab, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 4 |
|||
Word Break = [aab] |
|||
Word Break = [a, ab] |
|||
Word Break = [aa, b] |
|||
Word Break = [a, a, b] |
|||
String = aa b, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 0 |
|||
String = abcd, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 2 |
|||
Word Break = [abc, d] |
|||
Word Break = [a, b, c, d] |
|||
String = abbc, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 1 |
|||
Word Break = [a, b, b, c] |
|||
String = abcbcd, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 3 |
|||
Word Break = [abc, b, c, d] |
|||
Word Break = [a, b, cb, c, d] |
|||
Word Break = [a, b, c, b, c, d] |
|||
String = acdbc, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 2 |
|||
Word Break = [ac, d, b, c] |
|||
Word Break = [a, c, d, b, c] |
|||
String = abcdd, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 2 |
|||
Word Break = [abc, d, d] |
|||
Word Break = [a, b, c, d, d]</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |