LintCode 496 · Toy Factory.py

	"""
	Your object will be instantiated and called as such:
	ty = ToyFactory()
	toy = ty.getToy(type)
	toy.talk()
	"""
	# Simulation OOP
	class Toy:
	def talk(self):
	raise NotImplementedError('This method should have implemented.')
	class Dog(Toy):
	# Write your code here
	def talk(self):
	print("Wow")
	class Cat(Toy):
	# Write your code here
	def talk(self):
	print("Meow")
	class ToyFactory:
	# @param {string} Type a string
	# @return {Toy} Get object of the type
	def getToy(self, type):
	# Write your code here
	if type == 'Dog':
	return Dog()
	elif type == 'Cat':
	return Cat()
	else:
	return None

view raw LintCode 496 · Toy Factory.py hosted with ❤ by GitHub

LintCode 97 · Maximum Depth of Binary Tree.py

	"""
	Definition of TreeNode:
	class TreeNode:
	def __init__(self, val):
	self.val = val
	self.left, self.right = None, None
	"""
	# Approach #1 - DFS - T O(n), S O(h), with n being #OfNodes, h being the depth.
	class Solution:
	"""
	@param root: The root of binary tree.
	@return: An integer
	"""
	def maxDepth(self, root):
	# write your code here
	if root is None:
	return 0
	return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

view raw LintCode 97 · Maximum Depth of Binary Tree.py hosted with ❤ by GitHub

LintCode 1178 · Student Attendance Record I.py

	# Approach #1 - Simulation, String - T O(n), S O(1)
	class Solution:
	"""
	@param s: a string
	@return: whether the student could be rewarded according to his attendance record
	"""
	def checkRecord(self, s):
	# Write your code here
	# if As > 1 or consective Ls > 2, false, otherwise true
	countA, countL = 0, 0
	for ch in s:
	if ch == 'A':
	countA += 1
	if countA > 1:
	return False
	countL = 0
	elif ch == 'L':
	countL += 1
	if countL > 2:
	return False
	else:
	countL = 0
	return True

view raw LintCode 1178 · Student Attendance Record I.py hosted with ❤ by GitHub

LintCode 1 · A + B Problem.py

	class Solution:
	"""
	@param a: An integer
	@param b: An integer
	@return: The sum of a and b
	"""
	def aplusb(self, a, b):
	# write your code here
	return a + b

view raw LintCode 1 · A + B Problem.py hosted with ❤ by GitHub

LintCode 39 · Recover Rotated Sorted Array.java

	// Approach #1 - 3-way flipping - T O(n), S O(1)
	public class Solution {
	/**
	* @param nums: An integer array
	* @return: nothing
	*/
	public void recoverRotatedSortedArray(List<Integer> nums) {
	// handle corner cases
	if (nums == null || nums.size() == 0) {
	return;
	}
	int n = nums.size();
	int endingIndex = n - 1;
	for (int i = 0; i < n - 1; i++) {
	if (nums.get(i) > nums.get(i + 1)) {
	endingIndex = i;
	break;
	}
	}
	// reverse left
	reverse(nums, 0, endingIndex);
	// reverse right
	reverse(nums, endingIndex + 1, n - 1);
	// reverse the whole thing
	reverse(nums, 0, n - 1);
	return;
	}
	private void reverse(List<Integer> nums, int left, int right) {
	while (left < right) {
	Integer tmp = nums.get(left);
	nums.set(left, nums.get(right));
	nums.set(right, tmp);
	left++;
	right--;
	}
	}
	}

view raw LintCode 39 · Recover Rotated Sorted Array.java hosted with ❤ by GitHub

LintCode 423 · Valid Parentheses.java

	// Approach #1 - T O(n), S O(n), given that n is the length of the input string.
	// Error-prone: Character instead of Characters
	public class Solution {
	/**
	* @param s: A string
	* @return: whether the string is a valid parentheses
	*/
	public boolean isValidParentheses(String s) {
	// write your code here
	if (s == null || s.length() == 0) {
	return true;
	}
	Stack<Character> stack = new Stack<>();
	for (int i = 0; i < s.length(); i++) {
	char letter = s.charAt(i);
	if (isOpening(letter)) {
	stack.push(letter);
	} else {
	if (stack.isEmpty()) {
	return false;
	} else if (isMatching(stack.peek(), letter)) {
	stack.pop();
	} else {
	return false;
	}
	}
	}
	if (!stack.isEmpty()) {
	return false;
	}
	return true;
	}
	private boolean isOpening(char ch) {
	return (ch == '(' || ch == '[' || ch == '{');
	}
	private boolean isMatching(char ch1, char ch2) {
	return (ch1 == '{' && ch2 == '}') || (ch1 == '(' && ch2 == ')') || (ch1 == '[' && ch2 == ']');
	}
	}

view raw LintCode 423 · Valid Parentheses.java hosted with ❤ by GitHub

LintCode 442 · Implement Trie (Prefix Tree).java

	// Approach #1 - Trie - Data Structure implementation.
	// T O(h) for all the 3 searching functions, given that h is the height of the tree.
	public class Trie {
	private TrieNode root;
	public Trie() {
	// do intialization if necessary
	root = new TrieNode();
	}
	/*
	* @param word: a word
	* @return: nothing
	*/
	public void insert(String word) {
	// write your code here
	TrieNode node = root;
	for (int i = 0; i < word.length(); i++) {
	char letter = word.charAt(i);
	if (!node.sons.containsKey(letter)) {
	node.sons.put(letter, new TrieNode());
	}
	node = node.sons.get(letter);
	}
	node.word = word;
	node.isWord = true;
	}
	/*
	* @param word: A string
	* @return: if the word is in the trie.
	*/
	public boolean search(String word) {
	// write your code here
	TrieNode node = root;
	for (int i = 0; i < word.length(); i++) {
	char letter = word.charAt(i);
	if (!node.sons.containsKey(letter)) {
	return false;
	}
	node = node.sons.get(letter);
	}
	return node.isWord;
	}
	/*
	* @param prefix: A string
	* @return: if there is any word in the trie that starts with the given prefix.
	*/
	public boolean startsWith(String prefix) {
	// write your code here
	TrieNode node = root;
	for (int i = 0; i < prefix.length(); i++) {
	char letter = prefix.charAt(i);
	if (!node.sons.containsKey(letter)) {
	return false;
	}
	node = node.sons.get(letter);
	}
	return true;
	}
	private class TrieNode {
	public String word;
	public boolean isWord;
	public Map<Character, TrieNode> sons;
	public TrieNode() {
	this.word = null;
	this.isWord = false;
	sons = new HashMap<>();
	}
	public TrieNode(String word, boolean isWord) {
	this.word = word;
	this.isWord = isWord;
	sons = new HashMap<>();
	}
	}
	}

view raw LintCode 442 · Implement Trie (Prefix Tree).java hosted with ❤ by GitHub