Looking for the title of a book that I read in the late '80s or early '90s. It was about a young woman who was a warrior and a princess with magic. She wore her hair in braids.
She was accompanied by a magical cat that she carried in a bag. The cat could speak to her and one time shapeshifted into a cloud cat.
She was also accompanied by a group of warriors on of which was actually from the race of her enemies. I believe they were called Tallahat or something like that.