Given a sentence, and a dictionary of words. Decode the sentence. Each word in the sentence has characters jumbled.

Input:
sentence: "isthsisettpntui"
dictionary: ["app", "apple", "is", "test", "set", "input", "this"]

Ouput: "this is test input"

Solution I proposed was preprocessing the dictionary as:
Create HashMap<String, int[]>, with key as word and val as count of chars.
Then apply backtracking to decode the sentence using char count logic.

Using hashmap seemed to be not optimal. I did not use Trie since the sentence was jumbled and would have required a Map anyways for mapping jumbled word to actual word(basically for each word sort by char and save to trie, and during backtracking the sentence sort the current substring and check in trie. But that again required a map with key=sorted word, value = original word)
How can we optimally implement this?

Related problem: https://leetcode.com/problems/word-break-ii/