Solved

# Scrabble Match

Posted on 2009-12-31
694 Views
Hi, I'm trying to write a regular expression that will search a word list for available words based on letters given (think scrabble).

Suppose my letters are "scuton", how would I match the word/words that contain as many of these letters are possible? Remember a letter can be used only once. Also, what if I have two s, such as "scutons", how would I match that case too, now s can be used twice.

Does that make sense?

Thanks,
Brian
0
Question by:BrianGEFF719

LVL 84

Accepted Solution

you won't know how many are possible until you search the entire list, so the best you can do with a regular expression is to look for a word containing a certain number of letters.  when you succeed with one number and fail at another number, that is the mist possible.
If you want to match a words that contain no other letters, that would be
\b[scuton]+\b
If you want to contain at least <number> of those letters, where it can also contain other letters, that would be
([scuton].*){<number>}
If you want to exclude words containing one of those letters twice that would be
(?!.*([scuton]).*\1)
If you want  exclude words containing 3 or more s
(?!(.*s){3})
0

LVL 51

Expert Comment

This feels more like a permutations problem than a regex problem.  There's no way to represent permutations in regex that I know of.  You can certainly generate a regex that handles all permutations, for example if you had the letters abc then this would match words in a dictionary using those letters.

^(a*b*c*|a*c*b*|b*a*c*|b*c*a*|c*a*b*|c*b*a*)\$

But the length of the expression will increase exponentially with the number of characters.

~bp
0

LVL 84

Expert Comment

^(a*b*c*|a*c*b*|b*a*c*|b*c*a*|c*a*b*|c*b*a*)\$
is equivalent to
^(?!.*(a[^a]+a|b[^b]+b|c[^c]+c|[^abc]))
which increases linearly with the number of characters.
0

LVL 84

Expert Comment

although strictly speaking, (?!...) is not a regular expression,
even if it is recognized by many programs that process regular expressions.
0

LVL 51

Expert Comment

Yes, I was trying to use the most basic regex syntax for my example, but do appreciate that things like Perl etc offer extensions to that.

~bp
0

LVL 19

Author Comment

Thank you for your help thus far. Here is what I'm doing using grep:

brian\$ cat MASTER | grep -E '\b[nsfroeak]+\b' | grep -Ev '\b.*(.).*(\1).*\b'

In this case my letters are nsfroeak, and I can have no repeated letters, if I can repeat an e, I am doing:

brian\$ cat MASTER | grep -E '\b[nsfroeak]+\b' | grep -Ev '\b.*([^e]).*(\1).*\b'

Can this be improved in anyway? I'm having troubles with the wildcard, meaning a tile that can be used for any letter. Is there anyway to integrate one "wildcard" letter into this regular expressions?

Thanks.
Brian

0

## Join & Write a Comment Already a member? Login.

by Batuhan Cetin Regular expression is a language that we use to edit a string or retrieve sub-strings that meets specific rules from a text. A regular expression can be applied to a set of string variables. There are many RegEx engines for u…
Whatever be the reason, if you are working on web development side,  you will need day-today validation codes like email validation, date validation , IP address validation, phone validation on any of the edit page or say at the time of registration…
Learn how to match and substitute tagged data using PHP regular expressions. Demonstrated on Windows 7, but also applies to other operating systems. Demonstrated technique applies to PHP (all versions) and Firefox, but very similar techniques will w…
Explain concepts important to validation of email addresses with regular expressions. Applies to most languages/tools that uses regular expressions. Consider email address RFCs: Look at HTML5 form input element (with type=email) regex pattern: T…

#### 728 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

#### Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!