Redirect Changed Permalink on wordpress

I assume you have added new permalink structure by defining Custom Permalink Structure on

https://yoursite.com/wp-admin/options-permalink.php

and added /%category%/%postname%/ in the custom structure field. This is the WordPress default/suggested method.

enter image description here

After this, you need to flush the old permalink structure by saving and reloading the permalink settings page.

This will not work for custom post type and only works for WordPress default post type. For custom post types you would have to apply additional hooks or defile it while registering custom post type function.

You should read the WordPress official documentation on using permalinks.

Update:

In this case, you can use “404_template” filter.

Example:

add_filter( '404_template', 'custom_redirect_to_category' );

function custom_redirect_to_category($template) {

    if ( ! is_404() ){
        return $template;
    }

    global $wp_rewrite;
    global $wp_query;

    if ( '/%category%/%postname%/' !== $wp_rewrite->permalink_structure ){
        return $template;
    }   

    if ( ! $post = get_page_by_path( $wp_query->query['category_name'], OBJECT, 'post' ) ){
        return $template;   
    }

    $permalink = get_permalink( $post->ID );

    wp_redirect( $permalink, 301 );
    exit;

}