Pages

Wednesday, July 17, 2013

Matching An Input String With A Given Dictionary

Questions about string matching are pretty often in interviews and this is one of them. I've seen two variations online: one to split the string in meaningful words and another one to determine all possible meaningful words that can be produced out of sub-strings of the input.

First one seems easy - you just go once through the string and output what you've matched, thus O(n) where n is the number of the input string's characters. Second one would involve trying all possible sub-words, which would be O(nk) where k is the length of the longest word.

Now another problem is how would you represent a dictionary. A hash map won't work here because there will be too many collisions and the hash map would loose its efficiency. The first solution here would be a trie and that's what I used in both mentioned problems. An example of an implementation of a trie can be found here




Now can it be done faster? Yes, we could use the Aho-Corasick string matching algorithm which uses a finite state machine that resembles to a trie. That will improve our time in the second problem from O(nk) to O(n), but don't forget that we have the pre-processing time. This may not be asked to be implemented in an interview, but it's good to mention.

8 comments:

  1. I am using this variant for PHP5. It's pretty fast and simple.

    ReplyDelete
  2. Daytime Emmy Awards daytime emmy awards 2019 tickets prices Scores Leading 27 Nominations The nominations for the 46th annual Daytime Emmy Awards were announced Wednesday during CBS' The Talk. CBS scored a leading 61 noms, followed by syndicated programs with 55 nods and Amazon Prime Video and Netflix, who tied with 49 mentions each. Among other outlets with double-digit noms, NBC received 38, followed by https://emmyawardsdaytime.com/daytime-emmy-awards-2019-tickets-prices/ ABC with 35, PBS with 31, YouTube.com with 20, Disney Jr. and Nickelodeon (tied with 16 each), HBO with 12 and Disney Channel with 10.

    The Hollywood Reporter's roundtable daytime emmy awards 2019 red carpet live series, Close Up With The Hollywood Reporter, was nominated for outstanding special class series, where the SundanceTV program will compete against CBS' Lucky Dog With Brandon McMillan, Oxygen's Mysteries & Scandals, Freeform's To Life: How Israeli https://emmyawardsdaytime.com/daytime-emmy-awards-2019-red-carpet-live/ Volunteers Are Changing the World, PBS' Variety Studio: Actors on Actors and AmericanTheatreWing.org's Working in the Theatre.

    The National Academy of Televisiondaytime emmy 2019 television academy Arts and Sciences, which presents the daytime TV honors, previously announced that chef Jacques Pepin and Judge Judy Sheindlin will receive lifetime-achievement honors this year. Sheindlin will be honored during the main ceremony, which is set to behttps://emmyawardsdaytime.com/daytime-emmy-2019-television-academy/ held Sunday, May 5, while Pepin will be recognized at the creative arts ceremony on May 3. Both events will take place at the Pasadena Civic Auditorium.

    ReplyDelete
  3. Bilal Akkawy world title fight: John Ryder canelo alvarez vs daniel jacobs tickets how to watch, fight date, undercard Australian boxer Bilal Akkawy will fight John Ryder for the interim WBA super middleweight world title at T-Mobile Arena in Las Vegas https://canelovsjacobsfights.com/canelo-alvarez-vs-daniel-jacobs-tickets/ on May 4 (May 5 in Australia0. The fight will take place on the undercard to Mexican superstar Saul 'Canelo' Alvarez's fight with Daniel Jacobs

    Canelo vs Jacobs, Beterbiev vs Kalajdzic, more  canelo alvarez vs daniel jacobs undercard Boxing fight times and TV schedule for April 30-May 4, 2019 DAZN, 2:00 pm ET, Canelo-Jacobs Grand Arrivals. At this event, if tradition is followed, fighters will get out https://canelovsjacobsfights.com/canelo-alvarez-vs-daniel-jacobs-undercard/ of cars and walk through crowds in Las Vegas, then say a few things when interviewed. BLH will have live coverage.

    The watch canelo vs jacobs full fight card live stream: how to watch the fight online from anywhere It's almost time for Canelo to meet the Golden Child. Saul Alvarez's WBA and WBC middleweight titles are on the line against Daniel Jacobs' IBF championsip. That's right https://canelovsjacobsfights.com/watch-canelo-vs-jacobs-full-fight-card/ it's a title unification fight and we'll tell you how to get a Canelo Alvarez vs Jacobs live stream, no matter where on Earth you are

    Alvarez vs Jacobs fight from canelo alvarez vs daniel jacobs ppv outside your country  In the US, UK or Canada tonight? Then scroll just a little further down this page and we'll tell you who's broadcasting the boxing from where you are.But if you're abroad https://canelovsjacobsfights.com/canelo-alvarez-vs-daniel-jacobs-ppv/ this weekend then you'll need another way to watch and avoid possible geo-blocking. That's where using a VPN comes in.

    ReplyDelete