I think that's ok if you have absolute paths mixed in.

If I have some long path like ~/src/open-source/dotfiles or /home/nick/src/open-source/dotfiles it all works with fuzzy matching. You can hit CTRL+r and then search for "cd dotfiles" and it finds it. The ~ isn't necessary, you can also do "^cd dotfiles"` for a tighter list of matches for paths that are more ambigious with other non-cd commands.