字典、文件系统与序列化

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def serialize(root) -> str:
    """Preorder with '#' for each missing child, comma-separated (LC 297)."""
    out = []

    def walk(node) -> None:
        if not node:
            out.append("#")
            return
        out.append(str(node.val))
        walk(node.left)
        walk(node.right)

    walk(root)
    return ",".join(out)


def deserialize(data: str):
    """The tree serialize() wrote: the tokens are read back in the same preorder."""
    tokens = iter(data.split(","))

    def build():
        t = next(tokens)
        if t == "#":
            return None
        node = TreeNode(int(t))
        node.left = build()  # left before right, as they were written
        node.right = build()
        return node

    return build()

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// Preorder with '#' for each missing child, comma-separated (LC 297).
string serialize(TreeNode* root) {
    if (!root) return "#";
    return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
}

// The tree serialize() wrote: the tokens are read back in the same preorder.
TreeNode* deserialize(const string& data) {
    size_t pos = 0;
    function<TreeNode*()> build = [&]() -> TreeNode* {
        size_t end = data.find(',', pos);
        if (end == string::npos) end = data.size();
        string t = data.substr(pos, end - pos);
        pos = end + 1;
        if (t == "#") return nullptr;
        TreeNode* node = new TreeNode(stoi(t));
        node->left = build();  // left before right, as they were written
        node->right = build();
        return node;
    };
    return build();
}

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Codec {
    private String[] tokens;
    private int next;

    // Preorder with '#' for each missing child, comma-separated (LC 297).
    String serialize(TreeNode root) {
        if (root == null) return "#";
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    // The tree serialize() wrote: the tokens are read back in the same preorder.
    TreeNode deserialize(String data) {
        tokens = data.split(",");
        next = 0;
        return build();
    }

    private TreeNode build() {
        String t = tokens[next++];
        if (t.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(t));
        node.left = build(); // left before right, as they were written
        node.right = build();
        return node;
    }
}

import (
	"strconv"
	"strings"
)

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// serialize writes the tree in preorder with "#" for each missing child, comma-separated (LC 297).
func serialize(root *TreeNode) string {
	if root == nil {
		return "#"
	}
	return strconv.Itoa(root.Val) + "," + serialize(root.Left) + "," + serialize(root.Right)
}

// deserialize rebuilds the tree serialize wrote, reading the tokens back in the same preorder.
func deserialize(data string) *TreeNode {
	tokens := strings.Split(data, ",")
	next := 0
	var build func() *TreeNode
	build = func() *TreeNode {
		t := tokens[next]
		next++
		if t == "#" {
			return nil
		}
		v, _ := strconv.Atoi(t)
		node := &TreeNode{Val: v}
		node.Left = build() // left before right, as they were written
		node.Right = build()
		return node
	}
	return build()
}

class MagicDictionary:
    """Does a word differ from some dictionary word in exactly one letter? (LC 676)"""

    def __init__(self, words: list[str]):
        self.root: dict = {}  # a trie of nested dicts; "$" marks the end of a word
        for w in words:
            node = self.root
            for ch in w:
                node = node.setdefault(ch, {})
            node["$"] = True

    def search(self, word: str) -> bool:
        def dfs(node: dict, i: int, changed: bool) -> bool:
            if i == len(word):
                return changed and "$" in node  # exactly one change, ending on a word
            for ch, child in node.items():
                if ch == "$":
                    continue
                if ch == word[i]:
                    if dfs(child, i + 1, changed):
                        return True
                elif not changed and dfs(child, i + 1, True):  # spend the one change here
                    return True
            return False

        return dfs(self.root, 0, False)

// Does a word differ from some dictionary word in exactly one letter? (LC 676)
class MagicDictionary {
    struct Node {
        Node* next[26] = {};
        bool end = false;  // a dictionary word ends here
    };
    Node root;

    bool dfs(const Node* node, const string& word, size_t i, bool changed) const {
        if (i == word.size()) return changed && node->end;  // exactly one change, ending on a word
        for (int c = 0; c < 26; c++) {
            const Node* child = node->next[c];
            if (!child) continue;
            if (c == word[i] - 'a') {
                if (dfs(child, word, i + 1, changed)) return true;
            } else if (!changed && dfs(child, word, i + 1, true)) {  // spend the one change here
                return true;
            }
        }
        return false;
    }

public:
    explicit MagicDictionary(const vector<string>& words) {
        for (const string& w : words) {
            Node* node = &root;
            for (char ch : w) {
                if (!node->next[ch - 'a']) node->next[ch - 'a'] = new Node();
                node = node->next[ch - 'a'];
            }
            node->end = true;
        }
    }
    bool search(const string& word) const { return dfs(&root, word, 0, false); }
};

// Does a word differ from some dictionary word in exactly one letter? (LC 676)
class MagicDictionary {
    private static class Node {
        final Node[] next = new Node[26];
        boolean end; // a dictionary word ends here
    }

    private final Node root = new Node();

    MagicDictionary(String[] words) {
        for (String w : words) {
            Node node = root;
            for (char ch : w.toCharArray()) {
                if (node.next[ch - 'a'] == null) node.next[ch - 'a'] = new Node();
                node = node.next[ch - 'a'];
            }
            node.end = true;
        }
    }

    boolean search(String word) {
        return dfs(root, word, 0, false);
    }

    private boolean dfs(Node node, String word, int i, boolean changed) {
        if (i == word.length()) return changed && node.end; // exactly one change, ending on a word
        for (int c = 0; c < 26; c++) {
            Node child = node.next[c];
            if (child == null) continue;
            if (c == word.charAt(i) - 'a') {
                if (dfs(child, word, i + 1, changed)) return true;
            } else if (!changed && dfs(child, word, i + 1, true)) { // spend the one change here
                return true;
            }
        }
        return false;
    }
}

type trieNode struct {
	next [26]*trieNode
	end  bool // a dictionary word ends here
}

// MagicDictionary answers whether a word differs from some dictionary word in exactly one letter (LC 676).
type MagicDictionary struct {
	root *trieNode
}

func NewMagicDictionary(words []string) *MagicDictionary {
	root := &trieNode{}
	for _, w := range words {
		node := root
		for i := 0; i < len(w); i++ {
			c := w[i] - 'a'
			if node.next[c] == nil {
				node.next[c] = &trieNode{}
			}
			node = node.next[c]
		}
		node.end = true
	}
	return &MagicDictionary{root}
}

func (d *MagicDictionary) Search(word string) bool {
	var dfs func(node *trieNode, i int, changed bool) bool
	dfs = func(node *trieNode, i int, changed bool) bool {
		if i == len(word) {
			return changed && node.end // exactly one change, ending on a word
		}
		for c, child := range node.next {
			if child == nil {
				continue
			}
			if byte(c) == word[i]-'a' {
				if dfs(child, i+1, changed) {
					return true
				}
			} else if !changed && dfs(child, i+1, true) { // spend the one change here
				return true
			}
		}
		return false
	}
	return dfs(d.root, 0, false)
}