第七天:Leecode 394. Decode String

en.wikipedia.org

/*Author: ?Copyright by H.SenTime: 11/17/2017Main function: trie Tree(字典樹)Mode: C ++*///#include"stdafx.h"#include<iostream>using namespace std;const int TREE_WIDTH = 26;struct Node { int path; int end; char ch; Node *next[TREE_WIDTH]; Node(char ch = ) { this->ch = ch; this->path = this->end = 0; for (int i = 0; i < TREE_WIDTH; i++) { this->next[i] = nullptr; } }};class TrieTree {private: Node * root;public: TrieTree(); ~TrieTree(); void destroy(Node *t); int query(char *); void add(char *s); bool remove(char *s);};// implementationTrieTree::TrieTree() { root = new Node();}TrieTree::~TrieTree(){ destroy(root);}void TrieTree::destroy(Node *t) { for (int i = 0; i < TREE_WIDTH; ++i) { if (t->next[i]) destroy(t->next[i]); } delete t;}void TrieTree::add(char *s) { Node * t = root; while (*s) { if (t->next[*s - a] == nullptr) t->next[*s - a] = new Node(*s); t->next[*s - a]->path++; t = t->next[*s - a]; s++; } t->end++;}int TrieTree::query(char *s) { Node *t = root; while (*s) { if (t->next[*s - a] == nullptr || t->next[*s - a]->path == 0) return 0; t = t->next[*s-a]; s++; } return t->end;}bool TrieTree::remove(char * s) { if (query(s)) { Node * t = root; while (*s) { t->next[*s - a]->path--; t = t->next[*s-a]; s++; } t->end--; return true; } return false;}int main() { TrieTree tree; tree.add("strawberry"); tree.add("gradfather"); tree.add("policeman"); tree.add("breakfeast"); tree.add("mutton"); tree.add("bus"); tree.add("bus"); tree.add("bustop"); tree.add("computer"); cout << tree.query("bud") << endl; cout << tree.query("bus") << endl; cout << tree.remove("bustop") << endl; cout << tree.query("bustop") << endl; system("pause"); return 0;}

貴在堅持，堅持二字簡單卻可貴！

LeetCode 394:

Given an encoded string, return its decoded(解碼) string.

The encoding(編碼) rule is: k[encoded_string], where the encoded_string inside the square brackets[方括弧] is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid[有效的]; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there wont be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".s = "3[a2[c]]", return "accaccacc".s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

先思考一下，再來看看答案，對了，在這裡還給大家推薦一個編程網站，很適合國內程序員。