• 0

Determine if string can be split up into words


Question

I need to write an algorithm using dynamic programming to take an input in the form of a string without spaces or punctuation and return

a) if it can be split up into a sequence of words. "themailer" -> true; "thdfapple" -> false

b) the sequence produced. "the", "mailer"

In the dynamic programming approach, you have to find a subproblem... I've tried several with no avail... i feel like I'm closer right now with saying the subproblem is the longest word adjacent to the current position i'm testing

My general approach is to fill a table that is n x n long where n is the length of the string, the horizontal axis is the START of the substring and the vertical axis is the END of the substring (that i am testing)

Can anyone offer some insight / help on doing this? I realize this is highly esoteric and probably not explained very well... Sorry

9 answers to this question

Recommended Posts

  • 0

Hmm, that looks to be quite a challenge. You'd need some sort of dictionary to compare valid words to, but it might get a little interesting when you encounter words which could exist within other words, e.g. "ten" is a valid word, but so is "tenth". Unless you have a defined set of words and your work backwards (longest -> shortest) and break the string down that way? Never done anything like this before, so it would be interesting to see how you do it...

  • 0

If you want to do this with DYNAMIC PROGRAMMING you basically have to keep pointers of where your current words start/end and try to find a matching item. If the last word doesn't fit anywhere then try to move the previous one and so on.

  • Like 1
  • 0
  On 03/03/2010 at 20:38, Argote said:

If you want to do this with DYNAMIC PROGRAMMING you basically have to keep pointers of where your current words start/end and try to find a matching item. If the last word doesn't fit anywhere then try to move the previous one and so on.

That sounds like a good approach! Rather you than me though! Sounds very tricky indeed :rolleyes:

  • 0

The constraint is that it has to be done in O(n^2) time. Not quite sure what you mean Argote, but if your algorithm has to go back, then you might end up with n^n time because for every letter, you can have n mistakes.

I'm glad you seem to be familiar with dynamic programming though. I think I have a solution; perhaps you can verify that what I have runs in O(n^2) and is "dynamic programming"

pseudo python... the check to see if something is a word is considered to take unit time (that's just how it is.)

for start in range(0, length):
     for end in range(start+1, length):
         isWord = #check the current substring based on start and end.
         if isWord: table[start][end] = substring length

This should take n^2 time, according to a source, but it takes a little less since it only covers half of a table

due to the fact that end >= start is a constraint. This basically goes through all the substrings:

[a]bcd

[ab]cd

[abc]d

acd

a[bc]d (etc)

and when it hits one that is a word, it puts the length of that word into that cell (so to get the word, you trace the table UP that many rows)

I then propose to do a DEPTH FIRST SEARCH from the end of this table back, (as if it were a graph).

If I can get to the start state, then I can split the string up (and will have actually built it by then).

Depth First Search is O(|V| + |E|)... |V| = n, and |E| seems to be constrained to be n(n-1)=n^2-n in this case.

You have n nodes, and each node can have n-1 edges since it's basically an undirected graph.

so I have O(n^2 + n^2 -n) = O(n^2) runtime, I THINK....

please feel free to correct me or comment on it. I'm not sure if this is actually dynamic programming since I have to do a multipass (the DFS after I fill in the table)

This is my test string, by the way.... I hammered it out by combining interesting cases... it covers things such as choices like "than" or "thank" or "an"... "mail" or "mailer" or "email"

  thankillthemailer
t 00000000000000000
h 00000000000000000
a 00000000000000000
n 40000000000000000
k 50000000000000000
i 00000000000000000
l 00000000000000000
l 00004300000000000
t 00000000000000000
h 00000000000000000
e 00000000320000000
m 00000000430000000
a 00000000000000000
i 00000000000000000
l 00000000005400000
e 00000000000000000
r 00000000000600000

so the columns represent the START and the rows represent the END from my algorithm, so if you look at table['k','l'], you get a 4, which means that the 'l' is the end of a 4 letter word. (yes, i realize there are two l's, but it's easier to explain that way. i'm obviously talking about the second l)

  • 0

There is a much less complex and more elegant solution.

You propose to finish with a DFS working backwards to locate all solutions (paths through the directed graph back to the start). This itself is very close to the more elegant solution I will attempt to describe. We are indeed going to be starting at the end of the string rather than the beginning.

Let us call a string that has been successfully split into words a "sentence". Consider that every sentence must end with a word. Working from the end of the string forward, we will construct all valid sentences recursively.

Rather than iterating through all end and then all start positions, let us consider our end position static - we simply always end with the end of our "current" string as we are not interested in words ending before the end of our current string because those solutions don't provide a valid word at the end of the sentence. We will thus iterate only the start position, working backwards from end-1 to 0. If we ever get to start = 0 without finding a valid word, then there aren't any valid sentences because there are no valid words that the sentence can end with. We don't need to iterate again with a new end position, that would be wasted computation.

As we work backwards by start position, each time we encounter a valid word we will recurse with the substring preceding the word, and then prepend each result from the recursion to our "current" valid word to generate an array of our valid solution sentences. We don't recurse if start is 0 as we have reached the beginning of the string and can simply add the valid word to our array of solutions and return.

In pseudo-code (I have a running solution in PHP that I can generalize and post if there is interest, though it is much better left as an exercise for the reader)

 function find_sentences(string) {
     sentences = [];
     end = length(string) - 1;
     for (start = end; start >= 0; start--) {
         sublength = end - start + 1;
         substring = substring(string, start, sublength);
         if (is_word(substring)) {
             if (start > 0) {
                 next = substring(string, 0, start);
                 recurse = find_sentences(next);
                 foreach (recurse as result) {
                     sentences[] = result + ' ' + substring;
                 }
             } else {
                 sentences[] = substring;
             }
         }
     }
     return sentences;
 }

Enjoy! Any questions, I'll be happy to answer as best I can.

Also, thanks to ArmedMonkey - when I originally began on a solution for a similar problem, it was your solution that 'tipped' me off to the solution I described above.

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Posts

    • Download The Inclusion Equation: Leveraging Data & AI (worth $21) for free by Steven Parker Claim your complimentary eBook worth $21 for free, before the offer ends on June 24. The Inclusion Equation is a comprehensive, one-of-a-kind guide to merging DEI and employee wellbeing concepts with data analytics and AI. In this book, renowned thought leader and professional keynote speaker Dr. Serena Huang explains exactly how to quantify the effectiveness of new talent strategies by connecting them to a firm ROI estimate, enabling readers to approach and win the favor of higher-ups in any organization with the same effectiveness that marketing and financial departments do. This book is written in a style that is appealing and accessible to all readers regardless of technical background, but with enough depth to provide real insight and strategies. Dr. Serena H. Huang distills her 10 years of Fortune 500 people analytics leadership experience into tools and framework you can leverage to measure and improve DEI and wellbeing in your workplace. Some of the topics explored in this book include: Attract and retain top talent, including Gen Z and Millennials, with tailored DEI and wellbeing strategies Quantifying not only a talent strategy's perceived initial effect on an organization, but also its improvement and expansion over time Turning DEI and wellbeing from illusive corporate concepts to quantifiable metrics Harness the power of AI to create synchronized DEI and wellbeing strategies that maximize ROI Getting serious attention from your CEO and CFO by quantifying HR initiatives Using data storytelling to demonstrate the business impact of DEI and wellbeing Preparing for the future by understanding the role of AI in creating an inclusive and healthy workplace The Inclusion Equation is a complete guide for DEI and wellbeing, covering getting started in measurement to using storytelling to influence leadership. This is the contemporary playbook for any organization intending to substantially improve their diversity, equity, inclusion, and employee wellbeing by leveraging data & AI. This book is also perfect for any data analytics professionals who want to understand how to apply analytics to issues that keep their CEOs up at night. Whether you are a data expert or data novice, as long as you are serious about improving DEI and wellbeing, this book is for you. This free to download offer expires June 24. How to get it Please ensure you read the terms and conditions to claim this offer. Complete and verifiable information is required in order to receive this free offer. If you have previously made use of these free offers, you will not need to re-register. While supplies last! Download The Inclusion Equation: Leveraging Data & AI (worth $21) for free Offered by Wiley, view other free resources The below offers are also available for free in exchange for your (work) email: AI and Innovation ($21 Value) FREE – Expires 6/11 Unruly: Fighting Back when Politics, AI, and Law Upend [...] ($18 Value) FREE - Expires 6/17 SQL Essentials For Dummies ($10 Value) FREE – Expires 6/17 Continuous Testing, Quality, Security, and Feedback ($27.99 Value) FREE – Expires 6/18 VideoProc Converter AI v7.5 for FREE (worth $78.90) – Expires 6/18 Macxvideo AI ($39.95 Value) Free for a Limited Time – Expires 6/22 Excel Quick and Easy ($12 Value) FREE – Expires 6/24 The Inclusion Equation: Leveraging Data & AI ($21 Value) FREE – Expires 6/24 Microsoft 365 Copilot At Work ($60 Value) FREE – Expires 6/25 Natural Language Processing with Python ($39.99 Value) FREE – Expires 6/25 How to Engage Buyers and Drive Growth in the Age of AI ($22.95 Value) FREE – Expires 7/1 Using Artificial Intelligence to Save the World ($30.00 Value) FREE – Expires 7/1 Essential: How Distributed Teams, Generative AI, [...] ($18.00 Value) FREE – Expires 7/2 The Chief AI Officer's Handbook: Master AI leadership with strategies to innovate, overcome challenges, and drive business growth ($9.99 Value) FREE for a Limited Time – Expires 7/2 The Ultimate Linux Newbie Guide – Featured Free content Python Notes for Professionals – Featured Free content Learn Linux in 5 Days – Featured Free content Quick Reference Guide for Cybersecurity – Featured Free content We post these because we earn commission on each lead so as not to rely solely on advertising, which many of our readers block. It all helps toward paying staff reporters, servers and hosting costs. Other ways to support Neowin The above deal not doing it for you, but still want to help? Check out the links below. Check out our partner software in the Neowin Store Buy a T-shirt at Neowin's Threadsquad Subscribe to Neowin - for $14 a year, or $28 a year for an ad-free experience Disclosure: An account at Neowin Deals is required to participate in any deals powered by our affiliate, StackCommerce. For a full description of StackCommerce's privacy guidelines, go here. Neowin benefits from shared revenue of each sale made through the branded deals site.
    • It's basically been a rite of passage to blow up your first WSUS server by trying to sync the drivers database. Anyone who has done this has certainly seen the tens of thousands of driver packages and asked "what is all of this literal garbage?". Seems Microsoft is asking the same question. I do hope they won't take it too far and start removing drivers needed to run legacy systems, but there's definitely a happy medium to be found between "only the latest versions for actively supported hardware" and "every version of every driver ever for all time".
    • Stable..... No, he isn't..
    • Of course the sales are bad. Who even asked for a thinner phone with way less battery? Lightness? It's still a giant brick, it's just a thinner giant brick. It makes no sense at all. Making folding phones thinner, now that does make sense. Because when folded, the thinner it is unfolded, the more usable and pocketable it is when folded. You already expect worse battery at expense of actually being more pocketable. Galaxy Flip, when folded is half the size of S Ultra models and about as thick. That does make a big difference when fitting it in a pocket. But the phone that's as big as Ultra, making it thinner, you don't really solve anything, it's still a giant slab that barely fits into a pocket. All the "Mini" phones made way more sense than this thin crap. Especially now that it's literally impossible to find a phone smaller than 6.5". My dad only needs phone for calls and SMS and he doesn't want to go with smartphone because they are all so massive. Especially cheaper ones. Like, he'd be fine with Galaxy A06 for all he cares in terms of hardware, but it only comes in giant 6.7" format. It's useless. Or is he suppose to find a 800€ old gen iPhone Mini or Zenfone? He doesn't even need those stupid specs and such stupid price. And then you see old people fumbling around with giant smartphones and they don't even need 3/4 of features on them.
  • Recent Achievements

    • First Post
      emptyother earned a badge
      First Post
    • Week One Done
      Crunchy6 earned a badge
      Week One Done
    • One Month Later
      KynanSEIT earned a badge
      One Month Later
    • One Month Later
      gowtham07 earned a badge
      One Month Later
    • Collaborator
      lethalman went up a rank
      Collaborator
  • Popular Contributors

    1. 1
      +primortal
      664
    2. 2
      ATLien_0
      270
    3. 3
      Michael Scrip
      218
    4. 4
      Steven P.
      161
    5. 5
      +FloatingFatMan
      157
  • Tell a friend

    Love Neowin? Tell a friend!