Find longest word from dictionary based on offered letters C#

Question

1.00/5 (4 votes)

See more:

Hello everyone, please and need your help.
I have three text boxes on the windows form:
- In tetxBox1.Text there is a dictionary with many words (the longest words
have 12 letters)
- There are always 12 letters offered in textBox2.Text
- In textBox3.Text, I want the result to be longest word from textBox1
composed of offered letters from textBox2

For example:

In textBox1.Text I have the following words:

characters
character
charity
act
acter
acted
successfully
wind
succession
windy
successful
window
windows
success
excellent
excel
excellence
excellency

In textBox2.Text I have following 12 letters offered:

euclsfcysuls

In textBox3.Text I want as result longest word from textBox1.Text than letters from textBox2.Text:

successfully

I am asking for your help if it is possible, some solution...
I hope you understood me, I apologize for my English if you didn't understand.
Thank you all in advance.

https://i.postimg.cc/HnS59c2R/Capture.png[^]

What I have tried:

C#

static bool isSubSequence(String str1,
                                String str2)
        {
            int m = str1.Length, n = str2.Length;

            int j = 0; 

            for (int i = 0; i < n && j < m; i++)
            {
                if (str1[j] == str2[i])
                {
                    j++;
                }
            }
            return (j == m);
        }


static String findLongestString(List<String> dict,
                                            String str)
        {
            String result = "";
            int length = 0;
            foreach (String word in dict)
            {
                if (length < word.Length &&
                    isSubSequence(word, str))
                {
                    result = word;
                    length = word.Length;
                }
            }

            return result;
        }

private void btnfind_Click(object sender, EventArgs e)
        {
            String[] arr = textBox1.Lines;
            List<String> dict = new List<String>(arr);
            String str = textBox2.Text;
            textBox3.Text = (findLongestString(dict, str));
        }

Posted 28-Jan-24 11:41am

Member 10410972

Updated 28-Jan-24 13:00pm

PIEBALDconsult

v3

Add a Solution

Comments

Graeme_Grant 28-Jan-24 18:02pm

And? Where is the question?

Member 10410972 28-Jan-24 18:30pm

Thank you. The question is:
In textBox3.Text I want as result longest word from textBox1.Text than letters from textBox2.Text

In this example it would be the word: successfully

Please look at the picture from the link above, the picture says it all.
My code is not working...

PIEBALDconsult 28-Jan-24 19:08pm

Few people will click on a link.
And I don't think you want a subsequence.

PIEBALDconsult 28-Jan-24 19:06pm

Put the characters from box 2 in a HashSet (A).
For each word in box 1, put the characters in a HashSet (B).
If HashSet B is a subset of Hashset A, then note its length.
If more than one word from box 1 is a subset, then keep the longest.

Graeme_Grant 28-Jan-24 20:27pm

Also asked here: Find longest word from dictionary based on offered letters c# - Microsoft Q&A[^]

Peter_in_2780 29-Jan-24 2:10am

Smells to me like a class exercise.

PIEBALDconsult 29-Jan-24 17:17pm

It definitely sounds homeworkish and poorly defined.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2024-01-28T20:48:00

Think about the task instead of the solution: you need to find the longest set of matching words which have letters in common. So start by doing two things: build a map of characters (there are only 26 possibilities 'A' to 'Z' inclusive) and count them for both your "check letters" and your individual words.
So your example "euclsfcysuls" maps to:

A 0
B 0
C 2
D 0
E 1
F 1
G 0
H 0
I 0
J 0
K 0
L 2
M 0
N 0
O 0
P 0
Q 0
R 0
S 3
T 0
U 2
V 0
W 0
X 0
Y 1
Z 0

That's trivial: a single pass though a word counting the letters. Write a method to do that and test it thoroughly.

Now it's an easier problem: for each word to check, find how many match by comparing the letter counts: if the "possible word" has a letter count greater than the same "check word" letter, it's not a match.

As you go through, keep a "longest so far" word, and when you find a possible match, compare that against the "longest so far" and update as needed.

At the end, you have the longest possible match.

George Swan · Answer 2 · 2024-01-28T23:15:00

My suggestion would be to group all the letters in the target string into a collection of tuples where each tuple holds both a letter and the count of the total number of occurrences of that letter. There is a linq method that can do this.

C#

string target = "euclsfcysuls";
//group all the letters into a collection of tuples char key and key count
IEnumerable<(char Key, int count)> resultCollection = target.GroupBy(c => c).Select(g => (g.Key, g.Count()));

Iterate over the collection and add each key and letter count to a dictionary. Now, for each string in the test collection, group the letters in the same way as before but this time iterate over the test string groups. There is no match if the key letter is not present in the target dictionary or there are more repetitions of a letter than there is in the target string. The relevant code is something along these lines.

C#

bool isSuccessful = true;
foreach (var (key, count) in testCollection)
{
    //there is no match if the key char is not present in the target dict or
    //there are more repetitions of a letter  than in the target string
    if (targetDict.ContainsKey(key) is false || targetDict[key] < count)
    {
        isSuccessful = false;
        break;
    }
}
if (isSuccessful)
{
    matchedList.Add(testString);
}

Now all successful matches are in the matched list. Sort the list by the length of the strings in descending order. The winner is the first entry in the list.

PIEBALDconsult · Answer 3 · 2024-01-29T13:52:00

Here are my two offerings:

C#

private static bool
TryMatchHashSet
(
  string                                         Characters
,
  System.Collections.Generic.IEnumerable<string> Candidates
,
  out string                                     Result
)
{
  bool found = false ;

  Result = default(string) ;

  System.Collections.Generic.HashSet<char> h =
    new System.Collections.Generic.HashSet<char> ( Characters ) ;

  foreach ( string s in Candidates )
  {
    if ( h.IsSupersetOf ( s ) && ( !found || ( s.Length > Result.Length ) ) )
    {
      Result = s ;

      found = true ;
    }
  }

  return ( found ) ;
}

private static bool
TryMatchRegex
(
  string                                         Characters
,
  System.Collections.Generic.IEnumerable<string> Candidates
,
  out string                                     Result
)
{
  bool found = false ;

  Result = default(string) ;

  System.Text.RegularExpressions.Regex r ;

  try
  {
    r = new System.Text.RegularExpressions.Regex ( "^[" + Characters + "]+$" ) ;
  }
  catch
  {
    return ( found ) ;
  }

  foreach ( string s in Candidates )
  {
    if ( r.IsMatch ( s ) && ( !found || ( s.Length > Result.Length ) ) )
    {
      Result = s ;

      found = true ;
    }
  }

  return ( found ) ;
}

Find longest word from dictionary based on offered letters C#

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0