A scenario involving lepton-flavor-violating (LFV) interactions, either due to a LFV coupling of a scalar or a vector boson, is an intriguing beyond standard model (BSM) phenomenon. This LFV coupling in the presence of muons leads to a rich phenomenology including an extra contribution to muon anomalous magnetic moment. With the low-energy effective coupling $L_{\phi e\mu} = h_{e\mu}\phi\bar{e}(1 + \gamma^5) \mu$ + h.c., which turns electron into muon or vice versa through a scalar $\phi$, we first derive the ($h_{e\mu}$, $M_{\phi}$) parameter space that can account for experimental measurements of muon anomalous magnetic moment. We propose to probe such a parameter space or that with an even smaller $h_{e\mu}$ by searching for background-free processes of same-sign, same-flavor final-state lepton pairs $e^+ e^- \rightarrow e^\pm \mu^\mp \phi \rightarrow e^\pm e^\pm \mu^\mp \mu^\mp$ at Belle II experiment. Assuming such final states are detected by Belle II, we further propose an effective method to discriminate between scalar and vector boson-mediated LFV interactions based on significant differences in their event kinematic distributions.