A tiny markup language has only two kinds of tag: <name> opens an element and </name> closes it (names are lowercase letters). Everything outside tags is text. For a help-page indexer you need to know, for every piece of text, the chain of elements it sits inside.
Write text_paths(doc: str) -> list[tuple[str, str]] | None:
- Split the document into tags and text runs. A text run is a maximal stretch of characters between tags (or before the first / after the last tag). Strip spaces from both ends of each run and skip it if nothing is left.
- For every remaining run, in document order, output
(path, text), wherepathis the names of the currently open elements from outermost to innermost, joined with/. Text outside every element has path"". - If the tags don't nest properly, return
Noneinstead: a closing tag whose name isn't the innermost open element, a closing tag when nothing is open, or elements still open at the end.
text_paths("<note><to>Ana</to><body>Hi <b>there</b> friend</body></note>")
# [("note/to", "Ana"), ("note/body", "Hi"), ("note/body/b", "there"), ("note/body", "friend")]
text_paths("intro <p>x</p>") # [("", "intro"), ("p", "x")]
text_paths("<a><b>x</a></b>") # None (</a> arrives while <b> is innermost)
text_paths("<a>x") # None (<a> is never closed)
text_paths("") # []
len(doc) <= 10^6; aim for O(len(doc)). The characters<and>appear only as parts of well-formed tags, so you never need to handle a broken tag like<aor</>.- Elements can be nested thousands deep, so don't recurse: a Python list used as a stack keeps the open elements.
Show hint
walk the string with an index; at <, find the matching > with doc.find(">", i), then push the name for an opening tag or pop-and-compare for a closing one (doc[i + 1] == "/"). Before handling each tag, flush the text collected since the last tag.