Shuffling infinite sequences of 0s and 1s

Let $$f,g:\mathbb{Z}\to \{0,1\}$$ be maps such that the preimages of both 0 and 1 under both $$f$$ and $$g$$ are infinite, i.e. $$|f^{-1}(0)|=|f^{-1}(1)|=|g^{-1}(0)|=|g^{-1}(1)|=\infty.$$

In other words, if we think of $$f$$ and $$g$$ as infinite sequences of $$0$$'s and $$1$$'s, then both of these sequences contain infinitely many $$0$$'s and $$1$$'s.

Question: Does there exist a bijection $$\phi:\mathbb{Z}\to \mathbb{Z}$$ such that $$f\circ \phi =g$$?

For simple examples of $$f$$ and $$g$$ I can construct such a map $$\phi$$ explicitly. Does $$\phi$$ exist in general, and if so, how can this be shown? Does the existence of $$\phi$$ follow from the axiom of choice?

Yes, for given two functions $$\varphi_0:g^{-1}\{0\}\to f^{-1}\{0\}$$ and $$\varphi_1:g^{-1}\{1\}\to f^{-1}\{1\}$$. Since $$\Bbb Z=g^{-1}\{0\}\cup g^{-1}\{1\}$$ as disjoint union, there exists one and only one function $$\varphi:\Bbb Z\to\Bbb Z$$ extending both $$\varphi_0$$ and $$\varphi_1$$ and we have $$f\circ\varphi=g$$.
The condition \begin{align} &g^{-1}\{0\}\neq\varnothing\implies f^{-1}\{0\}\neq\varnothing& &g^{-1}\{1\}\neq\varnothing\implies f^{-1}\{1\}\neq\varnothing \end{align} is necessary and sufficient for the existence of such map $$\varphi$$.
Finally, the axiom of choice is not required, for if we pick $$a\in f^{-1}\{0\}$$ and $$b\in f^{-1}\{1\}$$, then we can take $$\varphi(x)= \begin{cases} a&g(x)=0\\ b&g(x)=1 \end{cases}$$