Graphs and String Manipulation - Medium LC

This problem is just laborious but requires a bit of work on Graphs (I usually build the graphs using Hashtables), traversal of graphs (in this case DFS) and string manipulation. Interesting that the standard String.CompareTo C# does not really compare lexicographically, at least when I used it, it failed for some test cases, so I had to build my own. Long code is down below, cheers, ACC.

Synonymous Sentences - LeetCode

1258. Synonymous Sentences

Medium

You are given a list of equivalent string pairs synonyms where synonyms[i] = [si, ti] indicates that si and ti are equivalent strings. You are also given a sentence text.

Return all possible synonymous sentences sorted lexicographically.

 

Example 1:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

Example 2:

Input: synonyms = [["happy","joy"],["cheerful","glad"]], text = "I am happy today but was sad yesterday"
Output: ["I am happy today but was sad yesterday","I am joy today but was sad yesterday"]

 

Constraints:

• 0 <= synonyms.length <= 10
• synonyms[i].length == 2
• 1 <= si.length, ti.length <= 10
• si != ti
• text consists of at most 10 words.
• The words of text are separated by single spaces.

public IList GenerateSentences(IList> synonyms, string text)
{
    Hashtable htSynonyms = CreateSynonymsHashtable(synonyms);
    Hashtable listOfSynonyms = new Hashtable();

    string[] words = text.Split(' ');
    foreach (string w in words)
    {
        if (!listOfSynonyms.ContainsKey(w))
        {
            List synonymsForWord = new List();
            GenerateListSynonyms(w, htSynonyms, new Hashtable(), synonymsForWord);
            SortWordsLex(synonymsForWord);
            listOfSynonyms.Add(w, synonymsForWord);
        }
    }

    List retVal = new List();
    ProcessSynonyms(words, 0, "", listOfSynonyms, retVal);

    return retVal;
}

public void GenerateListSynonyms(string from,
                                    Hashtable map,
                                    Hashtable wordVisited,
                                    List synonyms)
{
    if (wordVisited.ContainsKey(from)) return;

    wordVisited.Add(from, true);
    synonyms.Add(from);

    if (map.ContainsKey(from))
    {
        Hashtable localSynonyms = (Hashtable)map[from];
        foreach (string word in localSynonyms.Keys)
        {
            GenerateListSynonyms(word, map, wordVisited, synonyms);
        }
    }
}

public int CompareLex(string s1, string s2)
{
    int index1 = 0;
    int index2 = 0;

    while (index1 < s1.Length &&
            index2 < s2.Length)
    {
        if (s1[index1] == s2[index2])
        {
            index1++;
            index2++;
        }
        else
        {
            return (s1[index1] < s2[index2]) ? -1 : 1;
        }
    }

    if (index1 == index2) return 0;
    return (index1 < index2) ? -1 : 1;
}

public void SortWordsLex(List words)
{
    bool sorted = false;
    while (!sorted)
    {
        sorted = true;
        for (int i = 0; i < words.Count - 1; i++)
        {
            if (CompareLex(words[i], words[i + 1]) > 0)
            {
                sorted = false;
                string temp = words[i];
                words[i] = words[i + 1];
                words[i + 1] = temp;
            }
        }
    }
}

public Hashtable CreateSynonymsHashtable(IList> synonyms)
{
    Hashtable retVal = new Hashtable();

    foreach (List list in synonyms)
    {
        for (int i = 0; i < 2; i++)
        {
            if (!retVal.ContainsKey(list[i])) retVal.Add(list[i], new Hashtable());
            Hashtable connections = (Hashtable)retVal[list[i]];
            if (!connections.ContainsKey(list[(i + 1) % 2])) connections.Add(list[(i + 1) % 2], true);
        }
    }

    return retVal;
}

public void ProcessSynonyms(string[] wordsInText,
                            int currentIndex,
                            string currentText,
                            Hashtable listOfSynonyms,
                            List sentences)
{
    if (currentIndex >= wordsInText.Length)
    {
        sentences.Add(currentText.Trim());
        return;
    }

    string word = wordsInText[currentIndex];
    if (!listOfSynonyms.ContainsKey(word))
    {
        ProcessSynonyms(wordsInText, currentIndex + 1, currentText + " " + word, listOfSynonyms, sentences);
    }
    else
    {
        List listSynonyms = (List)listOfSynonyms[word];
        foreach (string w in listSynonyms)
        {
            ProcessSynonyms(wordsInText, currentIndex + 1, currentText + " " + w, listOfSynonyms, sentences);
        }
    }
}