Redirect 404 to new permalink structure

Our client has high positions in Google on some very popular keywords in their market. Because of the technical limitations of their custom CMS they asked us to build a WordPress website.

They also asked us to change the url structure of the product pages. For example:

http://www.site.com/cheap-tickets/ticket to http://www.site.com/tickets/cheap/ticket. This creates 404 pages to all ticket pages and causes lots of work to manually put 301 redirect to them.

So we need a 301 redirect that says: if a page under http://www.site.com/cheap-tickets/ gives a 404, then redirect to the matching ticket url under http://www.site.com/tickets/cheap/, else no 404 > show page.

Any ideas how to solve this?

Thanks!

https://wordpress.org/plugins/redirection/