Searching in Safari app on iOS 12.3.1 redirecting me to spam site
Shortly after updating to iOS 12.3.1, I did a rather innocuous search (something or other about product development success metrics) using the address/search bar at the top of the Safari app. One of the initial results, maybe the fifth or sixth one down, once tapped wound up being a spam site that loaded a pop-up and hijacked my browser. So I force quit the app immediately. Just to be clear here, I did not click any "DOWNLOAD NOW" links or any other obvious stuff like that, I simply went to a google search result and landed on what wound up being a nefarious page that had a very high SEO rank for the search I made, and did not interact with it at all. I am also saying this may not necessarily be the issue 100%, but it's the only time I ever landed on a site like this and the subsequent problem only occurred after it happened, so it's extremely likely.
Ever since then, whenever I do a specific search in Safari on my phone using the address/search bar (does not matter which search engine I have set to default, so long as it's done via the Safari address/search bar), it immediately redirects to a completely different website, in my case snapstream or something or other. Also in my case, it happens when I do a search in Safari for "Twitter search" (bc I deleted the Twitter app a while ago yet sometimes I search on that site to see what certain folks are saying…it's probably one of my most common searches). Not the biggest problem on its own so far but I have no idea what else this adware/malware is doing and am very nervous about having this on my device and want it off ASAP. I've always been pretty cautious with my devices and handling security, but as I said, this seems to stem from just tapping a pretty high up there search result in google that was indistinguishable from any of the other search results.
This is Safari, not Chrome. I already tried the Settings > Safari > Advanced > Website Data > Remove All Website Data that I've seen with similar results. I set Safari to Block All Cookies. Still happens. I went as far as resetting my phone to factory settings the other day when I first saw it, and starting from scratch (not a backup), which seemed okay for about twenty four hours, but I just tried it again a little bit ago and sure enough, the exact same thing happens. Same search term, same redirect spam site. Apparently something is installed that will not remove regardless of what I've done so far, even a factory reset, so looking to see what options I have from here.
iPhone SE, iOS 12