Discussion on "IP Validation Algorithm in Ruby"

Austin · 2023-06-06T17:33:32.858Z

Today we're gonna take a stab at a Medium LeetCode problem. For a long time I never even attempted these because I was worried that they'd be "too hard", but this example will demonstrate that this is not the case. Join me as we dive into the problem...

What's wrong with regex? The trick is to break it down into components that you can read without a brain double panic. A little string catenation at run time won't hurt, I promise

forums.craigslist.org

Yeah, converting that to OG line numbered BASIC isn't happening anytime soon 😂

Edit: Actually, those regexps match up pretty closely to how I'd approach the problem in old BASIC, even if I didn't have anything like InStr or IndexOf and could examine a string only one character at a time in a For loop. It might look a bit like a state machine or DFA

Austin The trick is, how do the .* know when to stop?

Or even "a*.a" when given "aaaa"

Austin I'm running into some not-fun parts now. Constructing the NFA isn't hard, but after that I'm between a rock and a hard spot. Running the equivalent DFA on the (potentially very large) input string is fast, but if the NFA has n states, the DFA could have up to 2ⁿ. Oof. Or you could run the NFA directly, but it could be in all n states for each character in the input string. n*m vs 2ⁿ, ouch

Search Hashnode

IP Validation Algorithm in Ruby

Responses1