StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>An excellent question and couple of hours of research and I think I have found the solution. First of all let me try explaining the question in a different approach.</p> <p><strong>Requirement:</strong></p> <p>Lets consider the same example 'common' (mainString) and 'cmn'(subString). First we need to be clear that any characters can repeat within the mainString and also the subString and since its pattern that we are concentrating on, the index of the character play a great role to. So we need to know:</p> <ul> <li>Index of the character (least and highest)</li> </ul> <p>Lets keep this on hold and go ahead and check the patterns a bit more. For the word common, we need to find whether the particular pattern cmn is present or not. The different patters possible with common are :- (Precedence apply )</p> <ul> <li>c -> o</li> <li>c -> m</li> <li>c -> n</li> <li>o -> m</li> <li>o -> o</li> <li>o -> n </li> <li>m -> m</li> <li>m -> o</li> <li>m -> n</li> <li>o -> n</li> </ul> <p>At any moment of time this precedence and comparison must be valid. Since the precedence plays a huge role, we need to have the index of each unique character Instead of storing the different patterns.</p> <p><strong>Solution</strong></p> <p>First part of the solution is to create a Hash Table with the following criteria :-</p> <ol> <li>Create a Hash Table with the key as each character of the mainString</li> <li>Each entry for a unique key in the Hash Table will store two indices i.e lowerIndex and higherIndex</li> <li>Loop through the mainString and for every new character, update a new entry of lowerIndex into the Hash with the current index of the character in mainString.</li> <li>If Collision occurs, update the current index with higherIndex entry, do this until the end of String</li> </ol> <p>Second and main part of pattern matching :-</p> <ol> <li>Set Flag as False</li> <li>Loop through the subString and for every character as the key, retreive the details from the Hash. </li> <li>Do the same for the very next character.</li> <li><p>Just before loop increment, verify two conditions</p> <pre><code>If highestIndex(current character) > highestIndex(next character) Then Pattern Fails, Flag <- False, Terminate Loop // This condition is applicable for almost all the cases for pattern matching Else If lowestIndex(current character) > lowestIndex(next character) Then Pattern Fails, Flag <- False, Terminate Loop // This case is explicitly for cases in which patterns like 'mon' appear </code></pre></li> <li><p>Display the Flag</p></li> </ol> <p>N.B : Since I am not so versatile in Java, I did not submit the code. But some one can try implementing my idea</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload