Various challenges in face recognition systems include partial occlusion, illumination, pose, and expression variations. Several face recognition systems have been proposed and obtained satisfactory performance under ideal conditions (Kortli et al. in Sensors 20:342, 2020). However, only some face recognition systems cope with the above challenges. Among all the challenges of face recognition, partial occlusion is the most challenging and less-studied research problem. Partial occlusion refers to hiding a part of one image with other objects like a scarf, mask, hat, beard, mobile, hand, and sunglasses. This paper proposes a novel approximation edit distance algorithm (AED) to match the partially occluded facial images. As part of the proposed work, faces are encoded into strings. The proposed AED algorithm accomplishes matching between input and database face image strings by determining the edit distance. AED algorithm also classifies input face images based on the approximated edit distance. In real-time scenarios, a face recognition database consists of millions of images. Matching a query image with the database gallery images requires much time. AED algorithm has less space and time complexity than the original edit distance algorithm. The proposed work was evaluated on AR and Extended Yale-B face databases. The results demonstrate that the proposed method performs significantly well for partially occluded facial image recognition.