I can definitely relate to this and for me, I value my freedom and privacy more than the convenience that proprietary apps give me so I just went back to the old fashioned way of searching up whatever lyrics I could identify. If it's an instrumental song, depending on where I am, I could sometimes ask an employee what playlist they were using.