Fountain codes are considered to be a promising coding technique in underwater acoustic communication (UAC) which is challenged with the unique propagation features of the underwater acoustic channel and the harsh marine environment. And Luby transform (LT) codes are the first codes fully realizing the digital fountain concept. However, in conventional LT encoding/decoding algorithms, due to the imperfect coverage (IC) of input symbols and short cycles in the generator matrix, stopping sets would occur and terminate the decoding. Thus, the recovery probability is reduced, high coding overhead is required and decoding delay is increased. These issues would be disadvantages while applying LT codes in underwater acoustic communication. Aimed at solving those issues, novel encoding/decoding algorithms are proposed. First, a doping and non-uniform selecting (DNS) encoding algorithm is proposed to solve the IC and the generation of short cycles problems. And this can reduce the probability of stopping sets occur during decoding. Second, a hybrid on the fly Gaussian elimination and belief propagation (OFG-BP) decoding algorithm is designed to reduce the decoding delay and efficiently utilize the information of stopping sets. Comparisons via Monte Carlo simulation confirm that the proposed schemes could achieve better overall decoding performances in comparison with conventional schemes.