Нужно ли в данной ситуации использовать регулярки или можно обойтись без них?

Я бы рекомендовал тут воспользоваться Map, где ключ - это String, а Value - это Char. Так будет работать быстрее и эффективней. И писать легче, как по мне. Но все зависит от того как полностью звучит задача и какие констрейнты

Здесь придётся каким-то образом "транслировать" свой паттерн в регулярку, сначала сопоставив буквы в паттерне с индексами соответствующих групп. Если считать, что слово (в простейшем случае) соответствует регулярному выражению \W+, то:

"abab" -> "(\\w+)\\W+(\\w+)\\W+\\1\\W+\\2" // a - 1, b -2
"abba" -> "(\\w+)\\W+(\\w+)\\W+\\2\\W+\\1"

При этом НЕ накладывается ограничение a != b

Возможная реализация:

public static boolean checkPattern(String pattern, String text) {
    Map<Character, Integer> groups = new HashMap<>();
    
    StringBuilder sb = new StringBuilder();
    
    int g = 1;
    for (char c : pattern.toCharArray()) {
        if (sb.length() != 0) {
            sb.append("\\W+");
        }
        if (!groups.containsKey(c)) {
            groups.put(c, g++);
            sb.append("(\\w+)");
        } else {
            sb.append("\\" + groups.get(c));
        }
    }
    return text.matches(sb.toString());
}

Тесты:

System.out.println(checkPattern("abab", "cat dog cat dog"));            // true
System.out.println(checkPattern("abba", "cat dog cat dog"));            // false
System.out.println(checkPattern("abba", "cat dog  dog cat"));           // true
System.out.println(checkPattern("acbbac", "cat dog rat rat  cat dog")); // true

Аналогичное решение, использующее String.join вместо StringBuilder и список для накопления групп в регулярке:

public static boolean checkPattern(String pattern, String text) {
    Map<Character, String> groups = new HashMap<>();
    List<String> rex = new ArrayList<>();
    
    for (char c : pattern.toCharArray()) {
        rex.add(groups.getOrDefault(c, "(\\w+)"));
        groups.putIfAbsent(c, "\\" + String.valueOf(groups.size() + 1));
    }

    return text.matches(String.join("\\W+", rex));
}