Honestly, the best way to do this is to run some queries on the database using regex to search and replace, after the database has been backed up of course.
Before learning more about SQL, I used this: https://interconnectit.com/products/search-and-replace-for-wordpress-databases/, which should work for you in this situation. You download the file, upload it to your public facing directory, and access the URL. Then you just use Regex to find the type of URLs you’re looking for, and then specify the replacement. Run it, and you’ll be good to go.
Don’t forget to delete it after using it though, if you do use it!