> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/design/road_trip.md).

# Road Trip

![](http://i.imgur.com/5masSeF.png)

* The idea:
  * Preform a preprocessing step that reads all the words from a dictionary, sorts it into a hash table that maps all anagrams that map to their words.
  * `{anagram} -> {vector of words that match anagram}`
  * Next, read the license-plates.
    * Sort the word in the plate, and map it to the anagram dictionary word. If the word does not appear, continuously add a new alpha character until a word is found in the dictionary.

```cpp
class wordAnagrams {
public:
    wordAnagrams(string filepath) {
        ifstream infile;
        infile.open(filepath);

        if (!infile.good()) {
            cout << "ERROR:\nBad filename.\n";
        }

        string sorted, unsorted;
        while (infile >> sorted) {
            unsorted = sorted;
            sort(sorted.begin(), sorted.end());

            // find the word
            if (anagrams.find(sorted) == anagrams.end()) {
                // not found
                vector<string> newVec;
                newVec.push_back(unsorted);
                anagrams.insert({ { sorted },{ newVec } });
            }
            // found
            else {
                anagrams.find(sorted)->second.push_back(unsorted);
            }
        }
    }

    vector<string> find(string word) {
        sort(word.begin(), word.end());
        if (anagrams.find(word) == anagrams.end()) {
            vector<string> empty;
            return empty;
        }
        return anagrams.find(word)->second;
    }

    string find_first(string word) {
        sort(word.begin(), word.end());
        if (anagrams.find(word) == anagrams.end()) {
            string empty = "";
            return empty;
        }
        return anagrams.find(word)->second.at(0);
    }

private:
    unordered_map<string, vector<string>> anagrams;
};


string get_next_word(string word, char current_add, wordAnagrams &anag) {
    string new_word = word + current_add;
    sort(new_word.begin(), new_word.end());
    return anag.find_first(new_word);
}

// removing digits from string
string extract_string(string str) {
    for (int i = 0; i < str.length(); i++) {
        if (isdigit(str.at(i)) || str.at(i) == ' ') {
            str.erase(i, 1);
            --i;
        }
        else str.at(i) = tolower(str.at(i));
    }

    return str;
}

vector<string> shortest_lic_word(string lic_filepath) {
    vector<char> alpha = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 
                          'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
    int cur_alpha = 0;
    int global_add = 0;

    string dict_filepath = "C:/Users/Gamer/Desktop/c++ daily/words.txt";
    wordAnagrams anagrams(dict_filepath);

    ifstream infile_lic;
    vector<string> shrt_words;
    infile_lic.open(lic_filepath);

    if (!infile_lic.good()) {
        cout << "ERROR:\nBad filename.\n";
    }
    string license;
    while (getline(infile_lic, license)) {
        // sort word
        license = extract_string(license);
        string shortest = anagrams.find_first(license);
        while (shortest.empty()) {
            shortest = get_next_word(license, alpha[cur_alpha++ % 26], anagrams);
            double current_add = double(cur_alpha) / 26;
            if (current_add == int(current_add)) {
                license += alpha[(cur_alpha + global_add) % 26];
                ++global_add;
                sort(license.begin(), license.end());
            }
        }
        shrt_words.push_back(shortest);
    }
    return shrt_words;
}


int main(int argc, char **argv) {
    //string dict_filepath = "C:/Users/Gamer/Desktop/c++ daily/words.txt";
    //wordAnagrams anagrams(dict_filepath);

    ///* ANAGRAM TEST */
    //string word = "cat";
    //vector<string> test = anagrams.find(word);
    //for (auto i : test) cout << i << " ";
    //cout << endl;
    //pause();

    string lic_filepath = "C:/Users/Gamer/Desktop/c++ daily/licenses.txt";
    vector<string> lic_words = shortest_lic_word(lic_filepath);
    print(lic_words);

}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/design/road_trip.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.