Еще одна сложная задача на написание собственного ограниченного движка регулярных выражений. Сначала попробуем применить наиболее логичный подход - класс Pattern, затем реализуем тривиальное решение, а затем решение на базе динамического программирования. 

Вступайте в группу в Telegram: http://t.me/java_weekly