Overcomplicating design patterns

I am trying to solve a design problem with design patterns. Now that I have the basics I am fairly sure that I overcomplicated it a lot. I seem to have multiple empty interfaces, and I probably could do with less with a different design. Also I'm not sure if future developers on the project will have an easy time figuring out this tangle.

I've made a mockup of the structure of the classes. The example is dumbed down to two service types (cf BaseAnimalService extensions), in the project there are more. There are also more BaseStrategy implementations.

At first I want do differentiate between a context for a CatService or DogService. This is done using a Map in the BaseStrategy class, which has the BaseAnimalService as value to enable polymorphism between the Cat/DogService. Based on the generic type of the BaseStrategy, implemented in the Dog/CatStrategy a different configurationMap is used, which in turn, based on the type of the criteria, loads one or the other implementation of the Dog/CatService. The configuration maps are defined in the spring.xml file.

Since the Dog/CatService both implement an extra interface, cf. SomeOtherCat/DogService, which is external to my design, the Dog/CatService both have have empty interfaces too. SomeOtherCatService and SomeOtherDogService aren't related and aren't editable so I can't use them polymorphically, which is the reason for the Base/Cat/DogService interfaces.

I thought about making the BaseStrategy a StrategyFactory which returns a Cat/DogStrategy which in turn checks the type of the criteria for which BaseAnimalService to use. But since both these strategies use the same logic for their strategies, this would mean I would have to create another base class.

What do you think? Any suggestions on what would be a better design for this problem? Or any improvements to the current one?

class BaseStrategy<T extends BaseAnimalService> {

    private ContextService contextService;
    private Map<String, BaseAnimalService> configurationMap;

    T getService() {
        return configurationMap.get(contextService.getCurrentContext());
    }
}

interface BaseAnimalService {
    //empty
}

interface DogService extends BaseAnimalService {
    //empty
}

interface CatService extends BaseAnimalService {
    //empty
}

class DogStrategy extends BaseStrategy<DogService> {
    //empty
}

class CatStrategy extends BaseStrategy<CatService> {
    //empty
}

class BritishShortHairServiceImpl implements CatService, SomeOtherCatService {
    @Override //source: SomeOtherCatService, same for other implementations below
    void pur() {
        //pur
    }
}

class LionServiceImpl implements CatService, SomeOtherCatService {
    @Override
    void pur() {
        //pur
    }
}

class PitBullServiceImpl implements DogService, SomeOtherDogService {
    @Override
    void wagTail() {
        //wag tail
    }
}

class ChihuahuaServiceImpl implements DogService, SomeOtherDogService {
    @Override
    void wagTail() {
        //wag tail
    }
}

class CatPerson {
    private BaseStrategy<CatService> catStrategy;

    void pet() {
        catStrategy.getService().pur();
    }
}

class DogPerson {
    private BaseStrategy<DogService> dogStrategy;

    void feed() {
        dogStrategy.getService().wagTail();
    }
}

Relevant spring.xml snippet:

<bean id="baseStrategy" abstract="true"
          class="com.animals.services.BaseStrategy">
        <property name="contextService" ref="contextService"/>
    </bean>

<bean id="catServiceStrategy"
          class="com.animals.services.CatStrategyImpl"
          parent="baseStrategy">
        <property name="strategyConfigurationMap">
            <map>
                <entry key="CONTEXT1" value-ref="britishShortHairService"/>
                <entry key="CONTEXT2" value-ref="lionService"/>
            </map>
        </property>
    </bean>

<bean id="dogServiceStrategy"
          class="com.animals.services.DogStrategyImpl"
          parent="baseStrategy">
        <property name="strategyConfigurationMap">
            <map>
                <entry key="CONTEXT1" value-ref="pitbullService"/>
                <entry key="CONTEXT2" value-ref="chihuahuaService"/>
            </map>
        </property>
    </bean>