Recursively padding 0's in names of files and folders

I have a folder containing video lectures on some particular topic. It is structured like this:

.
├── 1_fol
│   ├── 1_file.mp4
│   ├── 2_file.mp4
│   └── 3_file.mp4
└── 2_fol
    ├── 10_file.mp4
    ├── 4_file.mp4
    ├── 5_file.mp4
    ├── 6_file.mp4
    ├── 7_file.mp4
    ├── 8_file.mp4
    └── 9_file.mp4

I want to change this structure into

.
├── 001_fol
│   ├── 001_file.mp4
│   ├── 002_file.mp4
│   └── 003_file.mp4
└── 002_fol
    ├── 004_file.mp4
    ├── 005_file.mp4
    ├── 006_file.mp4
    ├── 007_file.mp4
    ├── 008_file.mp4
    ├── 009_file.mp4
    └── 010_file.mp4

This helps, because you can then use find . -regextype sed -regex ".*/.*\.\(mp3\|mp4\)" -print0 | sort -z | xargs -r0 vlc to open the whole playlist. I came up with a script to pad 0's, but it's quite lengthy and slow:

find . -depth -exec rename -v 's/(.*)\/([0-9]$)/$1\/00$2/;
      s/(.*)\/([0-9]{2}$)/$1\/0$2/;
      s/(.*)\/([0-9][^0-9][^\/]*$)/$1\/00$2/;
      s/(.*)\/([0-9]{2}[^0-9][^\/]*$)/$1\/0$2/' '{}' ';'

Can this be optimized further?

Edit
Actually, the execution became quite fast after the ';' was changed to '+'. But the set of regex(es) still looks quite ugly.

Solution

rename is a perl tool and allows you to use any perl expressions. The following perl expression searches for the last component of a path (for instance c in a/b/c) and pads its leading number (if existing) to three digits.

s/(^|\/)\K(\d+)(?=[^\/]*$)/sprintf "%03d",$2/e

Example:

1_fol/23_file.mp4 becomes 1_fol/023_file.mp4
1_fol becomes 001_fol
1_2/3_4.mp4 becomes 1_2/003_4.mp4
1_2 becomes 001_2

Use above perl expression in your find command for bash✱ ...

find -depth -exec rename 's/(^|\/)\K(\d+)(?=[^\/]*$)/sprintf "%03d",$2/ge' {} +

... or the extended globstar features in zsh. On my system globs were faster than find.

rename 's/(^|\/)\K(\d+)(?=[^\/]*$)/sprintf "%03d",$2/ge' **/*(On)

**/* recursively lists all files and directories and (On) reverses the order similar to -depth.

✱ For bash you still could use **/* with shopt -s globstar but reversing the order of the matched files is not so easy, so find is simpler and probably faster.