Fork me on GitHub

Posted on

We have learned the transactions in the database class, and we also know what the isolation level is. In this article, we would implement it all by our own.

Terminology

Record

The single entity in the database, anything that encapsulates something. for example file, json object

Collection

The set of Record

Transaction ID

The unique number of each transaction.

Implmentation

We implement our code all in python.

Framework

1
2
3
4
5
6
7
8
9
10
11
12
13
14
next_xid = 1
active_xids = set()
records = []

def new_transaction():
	global next_xid
    next_xid += 1
    active_xids.add(next_xid)
    return Transaction(next_xid)

class Transaction:
	def __init__(self, xod):
        self.xid= xid
        self.rollback_actions = []

Visibility and Locking

Then to express the visibility and the locking function of each record, we need to add tow extra pieces of information to the record, the detailed code is shown below:

1
2
3
4
5
6
7
8
9
10
class Transaction:
	def record_is_visible(self, record):
        
        if record['created_xid'] in active_xids and record['created_xid'] != self.xid:
            return False
        
        if record['expired_xid'] != 0 and (record['expired_xid'] not in active_xids or record['expired_xid'] == self.xid):
            return False
        
        return True
1
2
3
class Transaction:
    def row_is_locked(self, record):
        return record['expired_xid'] != 0 and row['expireed_xid'] in active_xids

Add a record

1
2
3
4
5
6
class Transaction:
	def add_record(self, record):
        record['created_xid'] = self.xid
        record['expired_xid'] = 0  ##Which means the record has never been deleted by anyone
        self.rollback_actions.append(["delete", len(records)]) ##This will be explained laterx
        records.append(record)

Deleting a record

1
2
3
4
5
6
7
8
9
class Transaction:
	def delete_record(self, id):
        for i, record in enumerate(records):
            if self.record_is_visible(record) and record["id"] == id:
                if self.row_is_lock(record):
                    raise Error("Row locked by another transaction.")
                else:
                    record['expired_xid'] = self.xid
                    self.rollback_actions.append(["add", i])  //This will be explained later

Updating a record

Updating can be splited into two procedures, deletion and appendix.

1
2
3
4
5
6
7
class Transaction:
	def update_record(self, id, name);
    	self.delete_record(id)
        self.add_record({
        	'id': id,
            'name': name
        })

Committing Changes

1
2
3
class Transaction:
	def commit(self):
        activate_xids.discard(self.xid)

Rollback Changes

1
2
3
4
5
6
7
8
9
class Transaction:
	def rolloback(self):
        for action in reversed(self.rollback_actions):
            if action[0] == 'add':
                records[action[1]]['expired_xid'] = 0
            elif action[0] == 'delete':
                records[action[1]]['expired_xid'] = self.xid
                
        active_xids.discard(self.xid)

Implement some isolation level

In this part I will implement two kinds of isolation level: repeatable read and seriealiztion

Extend transaction class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Transaction:	
    def __init__(self, table, xid):
        self.table = table
        self.xi = xid
        self.rollback_actions = []
        
    def add_record(self, id, name):
        record = {
            'id': id,
            'name': name,
            'created_xid': self.xid,
            'expired_xid': 0
        }
        self.rollback_actions.append(["delete", len(self.table.records)])
        self.table.records.append(record)
	
    def delete_record(elf, id):
        def delete_record(self, id):
        for i, record in enumerate(self.table.records):
            if self.record_is_visible(record) and record['id'] == id:
                if self.record_is_locked(record):
                    raise RollbackException("Row locked by another transaction.")
                else:
                    record['expired_xid'] = self.xid
                    self.rollback_actions.append(["add", i])
                    
   	def update_record(self, id, name):
        self.delete_record(id)
        self.add_record(id, name)
        
    def fetch_record(self, id):
        for record in self.table.records:
            if self.record_is_visible(record) and record['id'] is id:
                return record
		return None
    
    def count_records(self, min_id, max_id):
        count = 0
        for record in self.table.records:
            if self.record_is_visible(record) and \
                min_id <= record['id'] <= max_id:
                count += 1

        return count
    
    def fecth_all_records(self):
        visible_records = []
        for record in self.table.records:
            if self.record_is_visible(record);
            	visible_records.append(record)
                
        return visible_records
    
    
    def fetch(self, expr):
        visible_records = []
        for record in self.table.records:
            if self.record_is_visible(record) and expr(record):
                visible_records.append(record)

        return visible_records
    
    
    def commit(self):
        self.table.active_xids.discard(self.xid)
	
    def rollback(self):
        for action in reversed(self.rollback_actions):
            if action[0] == 'add':
                self.table.records[action[1]]['expired_xid'] = 0
            elif action[0] == 'delete':
                self.table.records[action[1]]['expired_xid'] = self.xid
		
        self.table.active_xids.discard(self.xid)

Based on the work above, we introduce the most simple isolation level ——— Read Uncommited

1
2
3
4
5
6
class ReadUncommittedTransaction(Transaction):
    def record_is_locked(self, record):
        return record['expired_xid'] != 0

    def record_is_visible(self, record):
        return record['expired_xid'] == 0

Then the case of read committed is a little complicated

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class ReadCommittedTransaction(Transaction):
    def record_is_locked(self, record):
        return record['created_xid'] != 0 and row['expired_xid'] in self.table.active_xids
    
    def record_is_visible(self, record):
        
        if record['created_xid'] in self.table.active_xids and record['created_xid'] != self.xid:
            return False
        
       if record['expired_xid'] != 0 and \
                (record['expired_xid'] not in self.table.active_xids or \
                record['expired_xid'] == self.xid):
                return False
            
         return True

Then the next level is Repeatable Read

1
2
3
4
5
6
7
8
9
10
11
12
class RepeatableReadTransaction(ReadCommittedTransaction):
    def record_is_locked(self, record):
        return ReadCommittedTransaction.record_is_locked(self, record) or \
            self.table.locks.exists(self, record['id'])
        
    def record_is_visible(self, record):
        is_visible = ReadCommittedTransaction.record_is_visible(self, record)
        
        if is_visible:
            self.table.locks.add(self, record['id'])

        return is_visible

Next step is to add a new class to manage all the lock

1
2
3
4
5
6
7
8
9
10
11
class LockManager:
	def __init__(self):
        self.locks = []
        
    def add(self, transaction, record_id):
        if not self.exists(transaction, record_id):
            self.locks.append([transaction, record_id])
            
    def exists(self, transaction, record_id):
        return any(lock[0] is transaction and lock[1] == record_id \
            for lock in self.locks)

Based on which, we can implement serializable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class SerializableTransaction(RepeatableReadTransaction):
    def __init__(self, table, xid):
        Transaction.__init__(self, table, xid)
        self.existing_xids = self.table.active_xids.copy()
	
    def record_is_visible(self, record):
        is_visible = ReadCommittedTransaction.record_is_visible(self, record) \
            and record['created_xid'] <= self.xid \
            and record['created_xid'] in self.existing_xids

        if is_visible:
            self.table.locks.add(self, record['id'])

        return is_visible

Posted on

You must have learned the yield in python before.Let’s say, we have the following code in python

1
2
3
4
5
6
7
8
def traverse(max):
    start = 0
    while start < max:
        yield start
        start += 1
        
for i in traverse(5):
    print (i)

The code above will print the 0,1,2,3,4,5

Of course the is the grammar sugar in python, the hack is coming—— how can we implement the code in C language?

Hack Begin

Considering jump, the first thing pop out from our mind is notorious goto isntruction. Regardless of the simplicity, we can introduce the goto to our first version of coroutine.

1
2
3
4
5
6
7
8
9
10
11
12
13
int function() {
    static int i, state = 0;
    switch(state) {
        case 0: goto LABEL0;
        case 1: goto LABEL1;
    }
    LABEL0:
    for (i = 0; i < 10; i ++){
        state = 1;
        return i;
         LABEL1:;
    }
}

Yet the goto is so ugly, let’s refract it with switch(in a way you have never seen before)

1
2
3
4
5
6
7
8
9
10
11
int function() {
    static int i, state = 0;
    switch(state) {
        case 0:
        for(i = 0; i < 1-; i++){
            state = 1;
            return i;
            case 1:;
        }
    }
}

Using line to universify it:

1
2
3
4
5
6
7
8
9
10
11
int function(void) {
  static int i, state = 0;
  switch (state) {
    case 0: /* start of function */
    for (i = 0; i < 10; i++) {
      state = __LINE__ + 2; /* so we will come back to "case __LINE__" */
      return i;
      case __LINE__:; /* resume control straight after the return */
    }
  }
}

The next step is the most important one

1
2
3
4
5
6
7
8
9
10
11
12
#define Begin() static int state = 0; switch(state) {case 0;
#define Yield(x) do {state = __LINE__; return x; case __LINE__:;} while(0)
#define End() }


int function(void) {
  static int i;
  Begin();
  for (i = 0; i < 10; i++)
    Yield(i);
  End();
}

Now, I would like to introduce a new continuation implementation based on the spark above, you can checkout at the

Posted on

Skeleton of the Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T>
class SList { 
   private: 
       typedef struct Node { 
            T data;
            Node *next;
            Node(T& data) : value(data), next(NULL) { }
       } Node; 
       pthread_mutex_t _lock;
       Node *head, *tail;  
   public: 
       void push_back(T& value);
       void insert_after(T& previous, T& value); // insert data after previous
       void remove(const T& value);
       bool find(const T& value);  // return true on success 
       SList(  );
       ~SList(  ); 
};

The implementation of push_back

1
2
3
4
5
6
7
8
9
10
11
void SList<T>::push_back(T& data) {
    pthread_mutex_lock(&_lock);
    if (head == NULL) {
        head = new Node(data);
        tail = head;
    }else {
        tail->next = new Node(data);
        tail = tail->next;
    }
    pthread_mutex_unlock(&_lock);
}

Drawback

Let’s consider the situation of batch insertion, this implementation will do harm to our efficiency becaue of the cost on lock(which requires the contet switch)

Yet a better way to insert item to linked list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SList<T>::push_back(T* data, int count) {
	Node *begin = new Node(data[0]);
	Node *temp = beging;
	for (int i = 1; i < count; i++) {
        temp->next = new Node(data[i]);
        temp = temp->next;
	}
	
	pthread_mutex_lock(&_lock);
	if(head == NULL) {
        head = begin;
        tail = head;
	}else {
        tail->next = begin;
        tail = temp;
	}
	pthread_mutex_unlock(&_lock);
}

Optimization for Searching Item

Considering when some process are doing iteration task, while the others is inserting or deleting.Some we need to classify these two situations, change or not change.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename T>
class SList {
private:
	typedef struct Node { 
       T data;
            Node *next;
            Node(T& data) : value(data), next(NULL) { } 
       } Node; 
       pthread_rwlock_t _rwlock; // Not pthread_mutex_t any more!
       Node *head, *tail;     
public:
	SList(  ) : head(NULL), tail(NULL) { 
           pthread_rwlock_init(&_rwlock, NULL);
       } 
       ~SList(  ) { 
           pthread_rwlock_destroy(&_rwlock);
           // … now cleanup nodes 
       } 
}

Search Code

1
2
3
4
5
6
7
8
9
10
11
12
13
bool SList<T>::find(const T& value){
    pthread_rwlock_rdlock (&_rwlock);
    Node* temp = head;
    while (temp) { 
         if (temp->value == data) {
              status = true;
              break;
         }
         temp = temp->next;
 
    pthread_rwlock_unlock(&_rwlock);
    return status;
}

Concurrent Insertion

To support current insertion, we need add the lock for each Node, so the new framework should be:

For the linked list, we assign a read-write lock. For each node in the linked list, we assign a mutex node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T>
class SList { 
   private: 
       typedef struct Node { 
           // … same as before 
       } Node; 
       pthread_rwlock_t _rwlock; // Not pthread_mutex_t any more!
       Node *head, *tail;  
   public: 
       // … other API remain as-is
       SList(  ) : head(NULL), tail(NULL) { 
           pthread_rwlock_init(&_rwlock, NULL);
       } 
       ~SList(  ) { 
           pthread_rwlock_destroy(&_rwlock);
           // … now cleanup nodes 
       } 
};

Add the read lock for searching, while add the mutex lock for the modified node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void SList<T>::insert_after(T& previous,T& value) {
    pthread_rwlock_rdlock(&_rwlock);
    Node* temp = head;
    while (temp) { 
         if (temp->value == previous) {
              break;
         }
         temp = temp->next;
    }
    Node* newNode = new Node(value);
     
    pthread_mutex_lock(&temp->lock);
    newNode->next = temp->next;
    temp->next = newNode;
    pthread_mutex_unlock(&temp->lock);
 
    pthread_rwlock_unlock(&_rwlock);
    return status;
}

Is lock necessary?

First let us introduce the CMPXCHG instruction on Intel chips, it is an atomic instruction but composed of serveral simple function. If we translate its function into C language:

1
2
3
4
5
6
7
int compare_and_swap ( int *memory_location, int expected_value, int new_value) 
{ 
  int old_value = *memory_location;
  if (old_value == expected_value) 
     *memory_location = new_value;
  return old_value;
}

This is short for compare and swap instruction. When you reach this, you must be curious about what the hell this is doing for?The answer is to design a lock free data structure.

Design a lock-free concurrent data structure

First let’s walk through the layout of to-be-designed data structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T> 
class Stack { 
    typedef struct Node { 
        T data;
        Node* next;
        Node(const T& d) : data(d), next(0) { } 
    } Node;
    Node *top; 
    public: 
       Stack( ) : top(0) { }
       void push(const T& data);
       T pop( ) throw (…); 
};

The implementation of push should use the CAS instruction. Let us paraphrase the __sync_bool_compare_and_swap(&top, n->next, n), which means that in each time we move the n to the next node, we need to check whether n->next == top, true means no other thread change the value of top, we can let the top point to the current top(n). Otherwise, we should redo the n->next =top to update the new top. 

1
2
3
4
5
6
7
8
9
void Stack<T>::push(const T& data){
    Node *n = new Node(data);
    while(1) {
        n->next = top;
        if (__sync_bool_compare_and_swap(&top, n->next, n)) { // CAS
            break;
        }
    }
}

Here we need to pay attention that the execution of __sync_bool_compare_and_swap is atomic for CPU, this is the prerequisite of our design.

For the same reason, we implement the pop function. In case of the system crush when we do the &top since top is NULL, we need to add the non_NULL check through the code.s

1
2
3
4
5
6
7
8
9
10
11
T Stack<T>::pop( ) 
{ 
    while (1) { 
        if (top == NULL) 
       		throw std::string(“Cannot pop from empty stack”);
        Node* next = top->next;
        if (top && __sync_bool_compare_and_swap(&top, top, next)) { // CAS
            return top->data;
        }
    }
}

Posted on

Linked List

Layout

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <pthread.h>
#include <list.h>
namespace concurrent {
    template <typename T>
    class Queue {
    public:
        Queue() {
            pthread_mutex_init(&_lock, NULL);
        }
        ~Queue() {
            pthread_mutex_destroy(&_lock);
        }
        void push(const T& data);
        T pop();
    private:
        list<T> _list;
        pthread_mutex_t _lock;
    }
}

Insert and Delete

Insertion

1
2
3
4
5
void Queue<T>::push(const T& value) {
    pthread_mutex_lock(&_lock);
    _list.push_back(value);
    pthread_mutex_unlock(&_lock);
}

Delete

1
2
3
4
5
6
7
8
9
10
T Queue<T>::pop() {
    if (_list.empty()){
        throw ”element not found”;
    }
    pthread_mutex_lock(&_lock);
    T _temp = _list.front();
    _list.pop_front();
    pthread_mutex_unlock(&_lock);
    return _temp;
}

Now let us consider a long list, and the situation is the reading thread is much moare that write thread

So we need to be more accurate about the granularity of the lock, Then let us redesign the whole class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T>
class Queue {
public:
	Queue() {
        pthread_mutex_init(&_rlock, NULL);
        pthread_mutex_init(&_wlock, NULL);
	}
	~Queue() {
        pthread_mutex_init(&_rlock);
        pthread_mutex_destroy(&_wlock);
	}
	void push(const T& data);
	T pop();
private:
	list<T> _list;
    pthread_cond_t _cond;
	pthread_mutex_t _rlock, _wlock;
}

Reimplement the push and pop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Queue<T>::push(const T& value) {
    pthread_mutex_lock(&_wlock);
    _list.push_back(value);
    pthread_mutex_unlock(&_wlock);
}

T Queue<T>::pop( ) { 
       if (_list.empty( )) { 
           throw ”element not found”;
       }
       pthread_mutex_lock(&_rlock);
       T _temp = _list.front( );
       _list.pop_front( );
       pthread_mutex_unlock(&_rlock);
       return _temp;
}

Then we addd the condition variable in pthread to concurrent queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typenmae T>
class BlockingQueue {
public:
	BlockingQueue() {
        pthread_mutex_init(&_lock, NULL);
        pthread_cond_init(&_cond, NULL);
	}
	~BlockingQueue() {
        pthread_mutex_destroy(&_lock);
        pthread_cond_destroy(&_cond);
	}
	void push(const T& data);
	T pop();
private:
	list<T> _list;
    pthread_mutex_t _lock;
    pthread_cond_t _cond;
}

The implementation of push

1
2
3
4
5
6
7
8
void BlockingQueue <T>::push(const T& value) {
	pthread_mutex_lock(&_lock);
	const bool was_empty = _list.empty();
	_list.push_back(value);
	pthread_mutex_unlock(&_lock);
	if (was_empty)
		pthread_cond_broadcast(&_cond);
}

The implementation of pop, pay attention to the while loop, it is aimed to prevent the fake resume of the process.

1
2
3
4
5
6
7
8
9
10
T BlockingQueue<T>::pop() {
    pthread_cond_wait(&_cond, &_lock);
    while(_list.empty()) {
        pthread_cond_wait(&_cond);
    }
    T _temp = _list.front();
    _list.pop_front();
    pthread_mutex_unlock(&_lock);
    return _temp;
}

Design a size-limited blocking queue

In the previous implementation, the size of the list is infinite. In this implementation, we will set a constant size for the queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typenmae T>
class BoundedBlockingQueue {
public:
	BoundedBlockingQueue(int size): maxSize(size) {
        pthread_mutex_init(&_lock, NULL);
        pthread_cond_init(&_rcond, NULL);
        pthread_cond_init(&_wcond, NULL);
        _array.reserve(maxSize);
	}
	~BounedBlockingQueue() {
        pthread_mutex_destroy(&_lock);
       pthread_cond_destroy(&_rcond);
       pthread_cond_destroy(&_wcond);
	}
	void push(const T& data);
	T pop();
private:
	vector<T> _array;
	int maxSize;
	pthread_mutex_t _lock;
    pthread_cond_t _rcond, _wcond;
}

Push item into a bounded queue

1
2
3
4
5
6
7
8
9
10
11
void BoundedBlockingQueue <T>::push(const T& value ) { 
	pthread_mutex_lock(&_lock);
	const bool was_empty = _array.empty();
	while (_array.size() == maxSize) {
        pthread_cond_wait(&_wcond, &_lock);
	}
	_array.push_back(value);
	pthread_mutex_unlock(&_lock);
	if (was_empty)
		pthread_cond_broadcast(&_rcond);
}

Pop item out of a bounded queue

1
2
3
4
5
6
7
8
9
10
11
12
13
T BoundedBlockingQueue<T>::pop() {
    pthread_mutex_lock(&_lock);
    const bool was_full = (_array.size( ) == maxSize);
    while(_array.empty( )) { 
        pthread_cond_wait(&_rcond, &_lock) ;
    }
    T _temp = _array.front( );
    _array.erase( _array.begin( ));
    pthread_mutex_unlock(&_lock);
    if (was_full)
    	pthread_cond_broadcast(&_wcond);
    return _temp;
}

Posted on

Linkage

https://leetcode.com/problems/find-the-duplicate-number/description/

This is a tricky question, we use binary search to solve it.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findDuplicate(int[] nums) {
        return findDuplicateIndex(nums, 0, nums.length - 1);
    }
    
    public int findDuplicateIndex(int[] nums, int small, int big) {
        if (small == big) return small;
        
        int biggerThanMiddleCount = 0;
        int middle = (small + big) / 2;
        int count = big - small + 1;
        for (int num : nums) {
            if (num > middle && num <= big)
                biggerThanMiddleCount += 1;
        }
        if (biggerThanMiddleCount <= count / 2)
            return findDuplicateIndex(nums, small, middle);
        else
            return findDuplicateIndex(nums, middle+1, big);
    }
}

Posted on

Linkage

https://leetcode.com/problems/surrounded-regions/description/

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public void solve(char[][] board) {
        int row_number = board.length;
        if (row_number == 0) return;
        int col_number = board[0].length;
        
        for (int i = 0; i < row_number; i++){
            search(board, i, 0);
            search(board, i, col_number - 1);
        }
        
        for (int j = 0; j < col_number; j++){
            search(board, 0, j);
            search(board, row_number - 1, j);
        }
        
        for (int i = 0; i < row_number; i++){
            for(int j = 0; j < col_number; j++){
                if(board[i][j] != 'M')
                    board[i][j] = 'X';
                else
                    board[i][j] = 'O';
            }
        }
    }
    
    public void search(char[][] board, int i, int j) {
        int row_number = board.length;
        int col_number = board[0].length;
        if (i < 0 || i >= row_number || j < 0 || j >= col_number || board[i][j] != 'O')
            return;
        
        board[i][j] = 'M';
        
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 
        for(int direction = 0; direction < 4; direction++){
            int row = i + directions[direction][0];
            int col = j + directions[direction][1];
            search(board, row, col);
        }
        return;
    }
    
}

Posted on

Linkage

https://leetcode.com/problems/word-break/description/

https://leetcode.com/problems/word-break-ii/description/

Analysis

In the first question, we just need to count the combination of wordBreak, but in the second question, we need to find out all the combination. To avoid TLE crisis because of a tricky case in Word Break II, we need to judge the first in advance.

Question I: Word Break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] ret = new boolean[s.length()+1];
        if (wordDict.size() == 0 || s.length() == 0) return false;
        
        ret[0] = true;
        for (int i = 1; i < s.length()+1; i++) {
            ret[i] = false;
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i < wordLength) continue;
                if (s.substring(i - wordLength, i).equals(word) && ret[i - wordLength] == true) 
                    ret[i] = true;
            }
        }
        return ret[s.length()];
    }
}

Question II: Word Break II

Naive code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        HashMap<Integer, LinkedList<String> > map = new HashMap<Integer, LinkedList<String> >();
        LinkedList<String> firstList = new LinkedList<String>();
        firstList.add(new String(""));
        map.put(0, firstList);
        for (int i = 1; i <= s.length(); i++) {
            LinkedList<String> ret_i = new LinkedList<String>();
            
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i < wordLength || s.substring(i-wordLength, i).equals(word) == false) continue;
                List<String> wordListStringList = map.get(i - wordLength);
                if (wordListStringList == null) continue;
                for (String wordListString : wordListStringList) {
                    String space = ( i == s.length() ? "": " "); 
                    String newWordListString = wordListString + word + space;
                    ret_i.add(newWordListString);
                }
            }
            map.put(new Integer(i), ret_i);
        }
        List<String> ret = map.get(s.length());
        return ret;
    }
}

To pass a very tricky but unmeaningful false case, we should judge whether there is a path prior to find path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public boolean whetherWordBreak(String s, List<String> wordDict) {
        boolean[] ret = new boolean[s.length()+1];
        if (wordDict.size() == 0 || s.length() == 0) return false;
        
        ret[0] = true;
        for (int i = 1; i < s.length()+1; i++) {
            ret[i] = false;
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i < wordLength) continue;
                if (s.substring(i - wordLength, i).equals(word) && ret[i - wordLength] == true) 
                    ret[i] = true;
            }
        }
        return ret[s.length()];
    }
    
    
    public List<String> wordBreak(String s, List<String> wordDict) {    
        if ( whetherWordBreak(s, wordDict) == false )
            return new LinkedList<String>();
        
        HashMap<Integer, LinkedList<String> > map = new HashMap<Integer, LinkedList<String> >();
        LinkedList<String> firstList = new LinkedList<String>();
        firstList.add(new String(""));
        map.put(0, firstList);
        
        
        for (int i = 1; i <= s.length(); i++) {
            LinkedList<String> ret_i = new LinkedList<String>();
            
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i < wordLength || s.substring(i-wordLength, i).equals(word) == false) continue;
                List<String> wordListStringList = map.get(i - wordLength);
                if (wordListStringList == null) continue;
                for (String wordListString : wordListStringList) {
                    String space = ( i == s.length() ? "": " "); 
                    String newWordListString = wordListString + word + space;
                    ret_i.add(newWordListString);
                }
            }
            map.put(new Integer(i), ret_i);
        }
        List<String> ret = map.get(s.length());
        return ret;
    }
}

So ugly!!!

Posted on

Linkage

https://leetcode.com/problems/coin-change/description/

https://leetcode.com/problems/unique-paths/description/

https://leetcode.com/problems/word-break/description/

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] ret = new int[m][n];
        if (m == 0 || n == 0) return 0;
        
        for(int i = 0; i < m; i++)
            ret[i][0] = 1;
        for(int j = 0; j < n; j++)
            ret[0][j] = 1;
        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++) {
                ret[i][j] = ret[i-1][j] + ret[i][j-1];
            }
        }
        return ret[m-1][n-1];
    }
}

Pay attention to the non-result case, once we found the amount i is unavailable, we should mark it with MAX, otherwise the min function will be executed wrongly. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int coinChange(int[] coins, int amount) {
        int [] ret = new int[amount+1];
        ret[0] = 0;
        for(int i = 1; i <= amount; i++) {
            int min_count = 100000;
            for (int coin : coins){
                if(coin > i) continue;
                min_count = Math.min(min_count, ret[i-coin] + 1);
            }
            ret[i] = min_count;
        }
        if (ret[amount] >= 100000)
            return -1;
        
        return ret[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] ret = new boolean[s.length()+1];
        if (wordDict.size() == 0 || s.length() == 0) return false;
        
        ret[0] = true;
        for (int i = 1; i < s.length()+1; i++) {
            ret[i] = false;
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i < wordLength) continue;
                if (s.substring(i - wordLength, i).equals(word) && ret[i - wordLength] == true) 
                    ret[i] = true;
            }
        }
        
        
        return ret[s.length()];
    }
}

Posted on

Description

https://leetcode.com/problems/unique-binary-search-trees-ii/description/

Code

Inspired by Unique Binary Search Trees, we use the divide and conquer strategy to solve the count of the different binary tree. In this quesiton, we can also apply this to the generation of trees.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> ret = new LinkedList<TreeNode>();
        if (n <= 0) {
            return ret;
        }
        return generatePartial(1, n);
    }
        
        
    public List<TreeNode> generatePartial(int start, int end) {
        
        List<TreeNode> ret = new LinkedList<TreeNode>();
        if (start > end) {
            ret.add(null);
            return ret;
        }
        for (int i = start; i <= end; i++){
            List<TreeNode> left_list = generatePartial(start, i - 1);
            List<TreeNode> right_list = generatePartial(i + 1, end);
            
            for(TreeNode left_root : left_list) {
                for (TreeNode right_root: right_list) {
                    TreeNode root = new TreeNode(i);
                    root.left = left_root;
                    root.right = right_root;   
                    ret.add(root);
                }
            }
        }
        return ret;
    } 
}

Posted on

Description

https://leetcode.com/problems/wildcard-matching/description/

Naive Code (TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    bool isMatch(string s, string p) {
        return findMatch(s, p, 0, 0);
    }
    
    bool findMatch(string s, string p, int s_index, int p_index) {
        if (s.length() == s_index && p_index == p.length()) return true;
        if (p_index == p.length()) return false;
        if (s_index == s.length()){
            if (p[p_index] == '*') {
                return findMatch(s, p, s_index, p_index + 1);
            }else {
                return false;
            }
        }
        
        char p_char = p[p_index], s_char = s[s_index];
        if (p_char == '?' || p_char == s_char) {
            return findMatch(s, p, s_index + 1, p_index + 1);
        }
        if (p_char == '*'){
            for(int i = s_index; i <= s.length(); i++) {
                if(findMatch(s, p, i, p_index + 1) ){
                    return true;
                }
            }
            return false;
        }
        
        return false;
    }
};