Question

How to check whether a string can be segmented into a sequence of words from a dictionary in VB.NET

Answer 1

Imports System
Imports System.Collections.Generic

Class Program
    Private Shared Function WordBreak(ByVal s As String, ByVal dict As HashSet(Of String)) As Boolean
        Dim slen As Integer = s.Length
        Dim result As List(Of Boolean) = New List(Of Boolean)(New Boolean(slen + 1 - 1) {})
        result(0) = True

        For i As Integer = 1 To slen

            For j As Integer = 0 To i - 1

                If result(j) AndAlso dict.Contains(s.Substring(j, i - j)) Then
                    result(i) = True
                    Exit For
                End If
            Next
        Next

        Return result(slen)
    End Function

    Public Shared Sub Main()
        Dim dict = New HashSet(Of String) From {
            "future",
            "depends",
            "the",
            "on",
            "your",
            "dreams",
            "start",
            "today"
        }
        Dim s As String = "futuredependsonyourdreams"

        If WordBreak(s, dict) Then
            Console.WriteLine("The string can be segmented")
        Else
            Console.WriteLine("The string cannot be segmented")
        End If
    End Sub
End Class



' run:
'
' The string can be segmented
'

 

70+ SQL courses for beginners and professionals

Answer 2

Imports System
Imports System.Collections.Generic

Class Program
    Private Shared Function IsInDict(ByVal word As String, ByVal dict As List(Of String)) As Boolean
        For Each entry In dict
            If entry = word Then Return True
        Next

        Return False
    End Function

    Private Shared Sub WordBreak(ByVal str As String, ByVal result As String, ByVal dict As List(Of String))
        Dim strsize As Integer = str.Length

        For i As Integer = 1 To strsize
            Dim subStr As String = str.Substring(0, i)

            If IsInDict(subStr, dict) Then

                If i = strsize Then
                    Console.WriteLine(result & subStr)
                    Return
                End If

                WordBreak(str.Substring(i), result & subStr & " ", dict)
            End If
        Next
    End Sub

    Public Shared Sub Main()
        Dim str As String = "butterflyplaybasketballwithbags"
        Dim dict As List(Of String) = New List(Of String) From {
            "butterfly",
            "basketball",
            "bagpiper",
            "and",
            "play",
            "with",
            "butter",
            "fly",
            "basket",
            "ball",
            "bags"
        }
        WordBreak(str, "", dict)
    End Sub
End Class



' run:
'
' butter fly play basket ball with bags
' butter fly play basketball with bags
' butterfly play basket ball with bags
' butterfly play basketball with bags
'

 

70+ SQL courses for beginners and professionals