Sachverhalt:
A.
B._ ist Eigentümerin der in der Kernzone der Gemeinde Zermatt gelegenen Parzelle GBV Nr. 777, Plan Nr. 5, im Ortsteil "Oberdorf". Diese weist einen Zweitwohnungsanteil von über 20 Prozent im Sinne des Zweitwohnungsgesetzes vom 20. März 2015 (ZWG; SR 702) auf.
Am 19. August 2016 reichte B._ bei der Gemeinde ein Baugesuch ein für den Abbruch zweier bestehender Häuser und die Erstellung von zwei Mehrfamilienhäusern. Im neuen Gebäude A sind zwei 71⁄2-Zimmerwohnungen ohne Nutzungsbeschränkung (nach Art. 11Abs. 2 ZWG i.V.m. <ref-law>) vorgesehen, im Gebäude B 13 Erstwohnungen mit entsprechender, im Grundbuch angemerkter Nutzungsbeschränkung.
B.
Die Gemeinde Zermatt erteilte die Baubewilligung am 23. Februar 2017. Dagegen erhoben die Stiftung Helvetia Nostra und A._ Beschwerde beim Staatsrat; sie befürchteten hinsichtlich der 13 geplanten Erstwohnungen eine Gesetzesumgehung. Der Staatsrat holte bei der Gemeinde einen Bericht über die Entwicklung der Bevölkerung, über die Anzahl der erstellten Erstwohnungen und das Verhältnis von Erst- und Zweitwohnungen im betreffenden Ortsteil "Oberdorf" ein. Diesen legte die Gemeinde am 18. August 2017 vor. B._ ihrerseits reichte einen von ihr mit der C._ AG abgeschlossenen, vom 15. Dezember 2017 datierenden Vertrag ein, wonach diese mindestens zehn der geplanten neuen Wohnungen zu ortsüblichen Konditionen mieten werde. Am 19. September 2018 wies der Staatsrat die Beschwerde ab.
Am 5. April 2019 wies das Kantonsgericht des Kantons Wallis eine Beschwerde von Helvetia Nostra und A._ ebenfalls ab.
C.
Dagegen haben Helvetia Nostra und A._ am 24. Mai 2019 beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Sie beantragen im Wesentlichen die Aufhebung des angefochtenen Entscheids und die Verweigerung der Baubewilligung.
B._ und die Gemeinde Zermatt beantragen die Abweisung der Beschwerde bzw. deren Abweisung, soweit darauf einzutreten sei. Das Kantonsgericht des Kantons Wallis schliesst ebenfalls auf Abweisung, unter Verweis auf den angefochtenen Entscheid. Der Staatsrat des Kantons Wallis verzichtet auf eine Stellungnahme. Das Bundesamt für Raumentwicklung (ARE) vertritt die Auffassung, es bestünden keine Hinweise auf eine Umgehung des ZWG oder auf einen offensichtlichen Rechtsmissbrauch. Am 24. Oktober 2019 haben die Beschwerdeführer eine weitere Stellungnahme eingereicht. Die Beschwerdegegnerin und die Gemeinde haben darauf repliziert.

Erwägungen:
1.
1.1. Angefochten ist ein kantonal letztinstanzlicher Endentscheid über eine baurechtliche Bewilligung (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Art. 90 BGG). Dagegen steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen; ein Ausschlussgrund nach <ref-law> liegt nicht vor. Damit ist die Beschwerde grundsätzlich zulässig.
1.2. Der Beschwerdeführer A._ macht geltend, seine Legitimation ergebe sich aus seiner Position als benachbarter Eigentümer. Weitere Angaben dazu macht er nicht: er führt nicht aus, welche Liegenschaft in seinem Eigentum stehen soll und belegt diese Behauptung auch nicht. Die Vorinstanz hat ihn ohne weiteres als beschwerdebefugt erachtet, dies aber ebenfalls nicht begründet. Ob A._ durch den angefochtenen Entscheid tatsächlich im Sinne von <ref-law> besonders berührt ist und ein schutzwürdiges Interesse an dessen Aufhebung hat, kann indessen offengelassen werden, denn die Beschwerdeführerin Helvetia Nostra ist offensichtlich zur Beschwerde befugt. Es handelt sich bei ihr um eine beschwerdeberechtigte Organisation im Bereich des Natur- und Heimatschutzes. Als solche ist sie zur Beschwerde gegen Verfügungen befugt, die in Erfüllung einer Bundesaufgabe im Sinne von <ref-law> und <ref-law> ergehen. Dazu gehört die Plafonierung des Zweitwohnungsbaus gemäss <ref-law>. Die Beschwerdeführerin kann daher Baubewilligungen wegen Verletzung von <ref-law> und seiner Ausführungsbestimmungen anfechten (<ref-ruling>). Auf die rechtzeitig erhobene Beschwerde ist daher einzutreten.
1.3. Die Beschwerdeführer haben ihre Eingabe in französischer Sprache verfasst, wozu sie befugt sind (<ref-law>). Das bundesgerichtliche Verfahren wird allerdings in der Regel in der Sprache des angefochtenen Entscheids geführt (<ref-law>), d.h. im vorliegenden Fall auf Deutsch. Davon abzuweichen, besteht kein Anlass, zumal sowohl die Beschwerdegegnerin wie auch die Gemeinde ihre Eingaben ebenfalls in deutscher Sprache verfasst haben.
2.
Streitig ist im vorliegenden Fall einzig, ob die Baubewilligung für das Gebäude B eine Umgehung des Zweitwohnungsverbots gemäss <ref-law> und <ref-law> darstellt. Danach dürfen in Gemeinden, in denen der Zweitwohnungsanteil über 20 Prozent liegt, keine neuen Zweitwohnungen bewilligt werden. Dies prüft das Bundesgericht frei (<ref-law>), grundsätzlich gestützt auf den von der Vorinstanz festgestellten Sachverhalt (Art. 105 Abs. 1 und 2 BGG).
2.1. Nach der neueren Rechtsprechung des Bundesgerichts ist von Amtes wegen zu prüfen, ob konkrete Indizien vorliegen, welche die Absicht bzw. die Möglichkeit einer Erstwohnungsnutzung des Bauvorhabens als unrealistisch erscheinen lassen. Die Möglichkeit, die Erstwohnnutzungsbeschränkung nach <ref-law> zu sistieren, erhöht das Risiko, dass die Bauherrschaft (trotz der restriktiven gesetzlichen Voraussetzungen) von vornherein auf eine künftige Sistierung setzt. Es würde dem Zweck des ZWG und von <ref-law> offensichtlich zuwiderlaufen, die Erstellung von Wohnungen zu bewilligen, die wahrscheinlich nie als Erstwohnungen genutzt werden können (<ref-ruling> E. 3 S. 101; <ref-ruling> E. 2.4 am Ende S. 54 f.).
2.2. Zu berücksichtigen sind (je nach den Umständen des Falls) die Lage der Liegenschaft (Bauzone, ganzjährige Zugänglichkeit, Distanz zu Arbeitsplätzen), die bauliche Gestaltung der Wohnungen aus Sicht einer ganzjährigen Nutzung, der Preis sowie die Verhältnisse der Person, welche dort zu wohnen beabsichtigt (aktueller Wohn- und Arbeitsort, Umzugsabsichten). Sind die künftigen Bewohner oder Bewohnerinnen nicht bekannt, ist die Nachfrage nach Erstwohnungen im gleichen Segment das Hauptkriterium (<ref-ruling> E. 3.1 S. 101; <ref-ruling> E. 2.2 S. 53; <ref-ruling> E. 3.2 S. 214). Diesfalls muss glaubhaft gemacht werden, dass im betreffenden Marktsegment eine Nachfrage für Erstwohnungen besteht (<ref-ruling> E. 3.1 S. 101; <ref-ruling> E. 2.3 S. 53; Urteil 1C_160/2015 vom 3. Mai 2016 E. 4.1). In Fällen, in denen die Nachfrage offensichtlich unzureichend ist, dürfen Baubewilligungen nur erteilt werden, wenn ernsthafte und konkrete Zusicherungen für den Erwerb durch ganzjährige Bewohner vorliegen (<ref-ruling> E. 3.1 S. 101; <ref-ruling> E. 2.4 S. 54). Dies gilt nach der Rechtsprechung selbst dann, wenn die Bauherrschaft die Absicht hat, das Bauvorhaben als Erstwohnungen zu vermarkten: Ist diese Absicht nicht realistisch, ist von einer Umgehung der gesetzlichen Regelung auszugehen. Diesfalls ist auch der Einwand unbeachtlich, wonach die Bauherrschaft das finanzielle Risiko trage (<ref-ruling> E. 3.1 S. 101; Urteil 1C_263/2016 vom 21. Februar 2017 E. 5.3 in fine).
3.
3.1. Die Vorinstanz hat festgestellt, die Bauparzelle befinde sich in der Kernzone der Gemeinde Zermatt, im Perimeter "Talkessel", knapp fünf Gehminuten vom Kirchplatz und vom Dorfzentrum entfernt. Es führe eine Buslinie daran vorbei mit einer Haltestelle in der Nähe. Das Grundstück befinde sich in dicht überbautem und erschlossenem Gebiet. Die geplanten Wohnungen schienen vom Zuschnitt, der Ausgestaltung, der Lage und Erschliessung für eine Erstwohnung geeignet; sie würden auch über keinen Fitnessraum oder Wellnessbereich verfügen. Diese Umstände bestreiten die Beschwerdeführer allesamt nicht. Sie sind daher für das Bundesgericht verbindlich (<ref-law>).
Gemäss den Erwägungen der Vorinstanz hat die ständige Wohnbevölkerung der Gemeinde zwischen dem 1. Januar 2013 und dem 1. November 2016 bloss um zehn Personen zugenommen. Es sei aber auch die Zahl der Erstwohnungsnutzer zu berücksichtigen. Am 1. November 2016 habe die Einwohnerzahl 5'671 betragen, diejenige der Erstwohnungsbenutzer dagegen 6'148. Diese Zahl sei bis zum 1. Januar 2017 auf 7'510 angestiegen. Dies bestätige, dass eine grosse Nachfrage nach Erstwohnungen bestehe. Dem Bericht der Gemeinde sei ausserdem zu entnehmen, dass zwar 74 Erstwohnungen nach <ref-law> bewilligt worden seien. Davon sei jedoch bloss ein kleiner Teil tatsächlich erstellt worden. Einige Baubewilligungen seien bereits verfallen, bei anderen Projekten sei die Realisierung ungewiss. Im zu beurteilenden Fall komme hinzu, dass die Bauherrschaft eine Vereinbarung mit der C._ AG abgeschlossen habe, welche mindestens zehn Wohnungen des Neubaus als Angestelltenwohnungen übernehmen werde. Es liege somit eine ernsthafte und konkrete Zusicherung für den Erwerb durch ganzjährige Bewohner vor, wie das Bundesgericht dies verlange.
3.2. Die Beschwerdeführer bezweifeln die oben angeführten Zahlen. Sie sind der Auffassung, es bestehe in Zermatt kein hinreichender Bedarf an Erstwohnungen, weshalb von einer Umgehung der Vorschriften des ZWG auszugehen sei. Die Vorbringen der Gemeinde betreffend die Bevölkerungsentwicklung hätten einfach überprüft werden können, denn nach der Walliser Gesetzgebung seien auch die Saisonniers verpflichtet, sich bei der Einwohnerkontrolle anzumelden. Die diesbezügliche Erwägung der Vorinstanz sei willkürlich, zumal die Hotelangestellten in der Regel auch in den Hotels wohnten. Wenn es - gemäss den Zahlen der Gemeinde - tatsächlich darum ginge, mehr als 1'000 Personen zusätzlich unterzubringen, wären zweifellos von den erteilten Baubewilligungen für Erstwohnungen Gebrauch gemacht worden. Auf der Internetplatform Comparis seien zahlreiche Wohnungen zum Kauf oder zur Miete ausgeschrieben.
Die Beschwerdeführer bezweifeln auch die Ernsthaftigkeit der Vereinbarung der Beschwerdegegnerin mit der C._ AG. Diese könne jedenfalls nicht mit einem Mietvertrag gleichgesetzt werden, weil dort weder die Dauer noch der Preis, die genau betroffenen Wohnungen oder die Kündigungsfristen bestimmt würden.
3.3. Die Beschwerdegegnerin führt in ihrer Antwort aus, sie habe mit der C._ AG, die bereits heute ihre Mieterin sei, für mindestens zehn der neu erstellten Wohnungen einen Vorvertrag zu einem Mietvertrag abgeschlossen. Bei der Mieterin handle es sich um ein Gastro-Unternehmen mit Sitz in Zermatt, das in drei Hotelbetrieben und vier Restaurants mehr als 120 Angestellte beschäftige, mit einem entsprechenden Bedarf an Personalwohnungen. Die neuen Wohnungen seien für Mitarbeitende dieses Unternehmens und ihre Familien geplant. Es handle sich um acht 31⁄2 bis 41⁄2-Zimmerwohnungen und fünf Studios. Die Vermietung werde zu ortsüblichen Konditionen erfolgen. Die heutige Mieterin habe ihre Zustimmung zur Auflösung der bestehenden Mietverträge nur unter der Bedingung gegeben, dass sie mindestens zehn der neuen Wohnungen nach Beendigung der Bauarbeiten wieder zu ortsüblichen Konditionen mieten könne und sie, die Beschwerdegegnerin, habe dem zugestimmt.
Das Angebot an Erstwohnungen in Zermatt sei sehr klein. Zu Beginn einer Sommersaison betrage die Leerwohnungsziffer 0,64 % und zu Beginn der Wintersaison 0,22 %. Die Gesuche für die 74 bewilligten Erstwohnungen seien zu einem grossen Teil vorsorglich eingereicht worden, dies angesichts der Rechtsunsicherheit nach der Volksabstimmung über <ref-law> und auch mit Blick auf mögliche Rückzonungen aufgrund der jüngsten Revision des Raumplanungsgesetzes.
3.4. In ihrer Stellungnahme bestätigt die Gemeinde diese Ausführungen im Wesentlichen. In Zermatt herrsche Wohnungsnot; die Nachfrage nach Erstwohnungen ergebe sich nicht aus einem markanten Bevölkerungswachstum, sondern aus einem dauerhaften Wohnungsmangel. Seit dem Jahr 2008 sei die Zahl der Beschäftigten um 45 % gestiegen; viele der Beschäftigten müssten zum Wohnen in eine Nachbarsgemeinde ausweichen. Ausserdem bestätigt die Gemeinde, dass die C._ AG in den bestehenden Gebäuden zwölf Wohnungen als Personalwohnungen gemietet habe.
4.
4.1. Das Bundesgericht hat sich mit dem Phänomen der rechtsmissbräuchlichen Umgehung der Bestimmungen des ZWG zur Einschränkung des Zweitwohnungsbaus kürzlich in den zwei publizierten - beide den Kanton Wallis betreffenden - Urteilen BGE <ref-ruling> (Gemeinde Bagnes) und BGE <ref-ruling> (Gemeinde Leytron) eingehend auseinander gesetzt. Demnach findet der offenbare Missbrauch eines Rechts gemäss dem für die gesamte Rechtsordnung geltenden <ref-law> keinen Rechtsschutz. Rechtsmissbrauch liegt vor, wenn ein Rechtsinstitut zweckwidrig zur Verwirklichung von Interessen verwendet wird, die dieses Rechtsinstitut nicht schützen will. Diesfalls muss die umgangene Norm angewendet werden, ungeachtet der rechtlichen Konstruktion, die zu ihrer Umgehung entwickelt worden ist. Um sanktioniert zu werden, muss der Missbrauch eines Rechts, wie sich für das Zivilrecht schon aus dem Wortlaut von <ref-law> ergibt, offensichtlich sein. Die Behörde, die beabsichtigt, die umgangene Norm anzuwenden, muss den Rechtsmissbrauch nachweisen oder zumindest ernsthaft diesbezügliche Hinweise aufzeigen. Es ist nicht einfach, die Umgehung abzugrenzen von der geschickten Nutzung einer vom Gesetz nicht ausgeschlossenen Möglichkeit. Dies zu entscheiden, erfordert eine Würdigung des Einzelfalls aufgrund der gesamten Umstände (vgl. BGE <ref-ruling> E. 2.2 S. 52; <ref-ruling> E. 2.5 S. 210).
4.2. Im vorliegenden Fall liegen keine eindeutigen Hinweise vor, um von einer Gesetzesumgehung auszugehen, geschweige denn von einem offensichtlichen Fall. Wie die Vorinstanz zurecht festhält, spricht insbesondere die bauliche Gestaltung der zu erstellenden Wohnungen nicht dafür, dass Zweitwohnungen geplant sind, weisen sie doch weder eine grosse Anzahl an Zimmern noch eine speziell grosse Wohnfläche auf, und es sind auch keine exklusiven, auf eine zahlungskräftige Kundschaft ausgerichteten Einrichtungen geplant. Zudem liegt die Bauparzelle im Ortszentrum und nicht am Rande des Siedlungsgebiets. Sie ist mit einer Buslinie gut erschlossen; aus allen diesen Gründen erscheinen die Wohnungen und Studios als Erstwohnungen geeignet. Der Fall liegt insofern grundlegend anders als im Urteil <ref-ruling>; dort handelte es sich um ein peripher gelegenes, mit dem öffentlichen Verkehr nur schwer erreichbares Grundstück, auf welchem Wohnungen von gehobenem Standard geplant waren, die aufgrund des voraussichtlichen Preises nur für wohlhabende Personen in Betracht kamen, zugleich aber für Erstwohnungen im gehobenen bzw. luxuriösen Segment klein dimensioniert waren. Schon vor diesem Hintergrund spricht wenig für eine Umgehungsabsicht der Beschwerdegegnerin.
4.3. Auf den Streitpunkt betreffend die Entwicklung der Wohnbevölkerung einerseits und derjenigen der verfügbaren Erstwohnungen andererseits braucht nicht vertieft eingegangen zu werden. Nach der oben dargestellten Rechtsprechung ist die generelle Nachfrage nach Erstwohnungen (im betreffenden Marktsegment) nur dann von Belang, wenn die künftigen Bewohner oder Bewohnerinnen der zu erstellenden Neubaute nicht bekannt sind. Dem liegt die Überlegung zugrunde, dass dann keine Umgehung des ZWG zu befürchten ist, wenn der Bauherrschaft und den Behörden die künftigen Bewohner bereits bekannt sind und diese sie als Erstwohnung zu nutzen beabsichtigen.
Im hier zu beurteilenden Fall sind die künftigen Bewohner des allein strittigen Gebäudes B zwar nicht namentlich bekannt. Angesichts der Vereinbarung zwischen der Beschwerdegegnerin und der C._ AG kann aber davon ausgegangen werden - und zwar ungeachtet der zivilrechtlichen Qualifikation dieses Vertrages -, dass letztere mindestens zehn dieser Wohnungen als Personalwohnungen für ihre Angestellten übernehmen wird. Den Beschwerdeführern ist zwar zuzugestehen, dass auch bei dieser Konstellation eine Umgehung der Bestimmungen betreffend die Zweitwohnungen nicht völlig auszuschliessen ist, zumal die genannte Vereinbarung erst während des Rechtsmittelverfahrens abgeschlossen worden ist. Es sprechen indes verschiedene Umstände gegen diese Befürchtung, so dass insgesamt nicht von einem Versuch der Umgehung der Regeln des Zweitwohnungsgesetzes ausgegangen werden muss. So ist zunächst bekannt, dass die C._ AG in der Gemeinde Zermatt ganzjährig mehrere Hotels und Restaurants betreibt, so dass ein Bedarf an Personalwohnungen ohne weiteres plausibel erscheint. Hinzu kommt, dass dieses Unternehmen gemäss den unbestritten gebliebenen Angaben der Beschwerdegegnerin in den abzubrechenden Bauten bereits heute eine grössere Zahl von Wohnungen für ihr Personal gemietet hat. Schliesslich ist auch nicht davon auszugehen, dass zur Täuschung der Behörden leichthin rein fiktive Vereinbarungen abgeschlossen und damit rechtlich erhebliche Tatsachen unrichtig beurkundet werden. Dies umso weniger, als die Gemeinde im bundesgerichtlichen Verfahren ihr Interesse am Bau von Erstwohnungen glaubhaft dargelegt hat und angenommen werden darf, dass sie gegen eine Umgehung der gesetzlichen Regelung einschreiten würde.
Von einem Rechtsmissbrauch beim Gesuch der Beschwerdegegnerin für den Bau von Erstwohnungen ist damit nicht auszugehen.
5.
Damit erweist sich die Beschwerde als unbegründet. Sie ist abzuweisen.
Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig (<ref-law>). Sie haben der anwaltlich verbeiständeten Beschwerdegegnerin zudem eine Parteientschädigung auszurichten (<ref-law>). Für beides haften sie solidarisch (Art. 66 Abs. 5 und Art. 66 Abs. 4 BGG). Die Gemeinde Zermatt obsiegt in ihrem amtlichen Wirkungskreis; sie hat keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern auferlegt.
3.
Die Beschwerdeführer entrichten der Beschwerdegegnerin eine Parteientschädigung von Fr. 4'000.--.
4.
Dieses Urteil wird den Parteien, der Einwohnergemeinde Zermatt, dem Staatsrat des Kantons Wallis, dem Kantonsgericht des Kantons Wallis, Öffentlichrechtliche Abteilung, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 28. Januar 2020
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Hänni