Freight drivers of electric trucks need to design charging strategies for where and how long to recharge the truck in order to complete delivery missions on time. Moreover, the charging strategies should be aligned with drivers' driving and rest time regulations, known as hours-of-service (HoS) regulations. This letter studies the optimal charging problems of electric trucks with delivery deadlines under HoS constraints. We assume that a collection of charging and rest stations is given along a pre-planned route with known detours and that the problem data are deterministic. The goal is to minimize the total cost associated with the charging and rest decisions during the entire trip. This problem is formulated as a mixed integer program with bilinear constraints, resulting in a high computational load when applying exact solution approaches. To obtain real-time solutions, we develop a rollout-based approximate scheme, which scales linearly with the number of stations while offering solid performance guarantees. We perform simulation studies over the Swedish road network based on realistic truck data. The results show that our rollout-based approach provides near-optimal solutions to the problem in various conditions while cutting the computational time drastically.