[LeetCode] Word Ladder I, II

Word Ladder I

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

思路：

LeetCode中为数不多的考图的难题。尽管题目看上去像字符串匹配题，但从“shortest transformation sequence from start to end”还是能透露出一点图论中最短路径题的味道。如何转化？

1. 将每个单词看成图的一个节点。
2. 当单词s1改变一个字符可以变成存在于字典的单词s2时，则s1与s2之间有连接。
3. 给定s1和s2，问题I转化成了求在图中从s1->s2的最短路径长度。而问题II转化为了求所有s1->s2的最短路径。

无论是求最短路径长度还是求所有最短路径，都是用BFS。在BFS中有三个关键步骤需要实现:

1. 如何找到与当前节点相邻的所有节点。
这里可以有两个策略：
(1) 遍历整个字典，将其中每个单词与当前单词比较，判断是否只差一个字符。复杂度为：n*w，n为字典中的单词数量，w为单词长度。
(2) 遍历当前单词的每个字符x，将其改变成a~z中除x外的任意一个，形成一个新的单词，在字典中判断是否存在。复杂度为：26*w，w为单词长度。
这里可以和面试官讨论两种策略的取舍。对于通常的英语单词来说，长度大多小于100，而字典中的单词数则往往是成千上万，所以策略2相对较优。

2. 如何标记一个节点已经被访问过，以避免重复访问。
可以将访问过的单词从字典中删除。

3. 一旦BFS找到目标单词，如何backtracking找回路径？



Word Ladder I

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

class Solution { public: int ladderLength(string start, string end, unordered_set<string> &dict) { dict.insert(end); queue<pair<string,int>> q; q.push(make_pair(start,1)); while(!q.empty()) { string s = q.front().first; int len = q.front().second; if(s==end) return len; q.pop(); vector<string> neighbors = findNeighbors(s, dict); for(int i=0; i<neighbors.size(); i++) q.push(make_pair(neighbors[i],len+1)); } return 0; } vector<string> findNeighbors(string s, unordered_set<string> &dict) { vector<string> ret; for(int i=0; i<s.size(); i++) { char c = s[i]; for(int j=0; j<26; j++) { if(c=='a'+j) continue; s[i] = 'a'+j; if(dict.count(s)) { ret.push_back(s); dict.erase(s); } } s[i] = c; } return ret; } };

Word Ladder II

[LeetCode新题] Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

思路：

找链表交界，很类似Linked List Cycle II那题，方法也是类似的双指针相遇法。分两步走：

1. 如何判断两链表是否相交？

两链表相交则他们必然有共同的尾节点。所以遍历两两链表，找到各自的尾节点，如果tailA!=tailB则一定不相交，反之则相交。

2. 如何判断两链表相交的起始节点？

在第1步判断相交时可以顺带计算两链表的长度lenA和lenB。让长的链表的head先走abs(lenA-lenB)步，然后和短链表的head一起走，直到两者相遇，即为要找的节点。

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

class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(!headA || !headB) return NULL; int lenA = 0, lenB = 0; ListNode *tailA = headA, *tailB = headB; while(tailA->next) { tailA = tailA->next; lenA++; } while(tailB->next) { tailB = tailB->next; lenB++; } if(tailA!=tailB) return NULL; if(lenA>lenB) { for(int i=0; i<lenA-lenB; i++) headA = headA->next; } else { for(int i=0; i<lenB-lenA; i++) headB = headB->next; } while(headA!=headB) { headA = headA->next; headB = headB->next; } return headA; } };

[LeetCode] First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

思路：

无序数组的题目如果要O(n)解法往往要用到hash table，但这题要求constant space。所以可以用数组本身作为一个"hash table"：A[0] = 1, A[1] = 2, .... A[n-1] = n。目标是尽可能将数字i放到数组第i-1个位置。

扫描数组中每个数：
1. 如果A[i]<1或者A[i]>n。说明A[i]一定不是first missing positive。跳过
2. 如果A[i] = i+1，说明A[i]已经在正确的位置，跳过
3. 如果A[i]!=i+1，且0<A[i]<=n，应当将A[i]放到A[A[i]-1]的位置，所以可以交换两数。
这里注意，当A[i] = A[A[i]-1]时会陷入死循环。这种情况下直接跳过。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public: int firstMissingPositive(int A[], int n) { int i=0; while(i<n) { if(A[i]!=i+1 && A[i]>0 && A[i]<=n && A[i]!=A[A[i]-1]) swap(A[i],A[A[i]-1]); else i++; } for(int i=0; i<n; i++) { if(A[i]!=i+1) return i+1; } return n+1; } };

[LeetCode] Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

思路：

Unix的path规则可以在这里了解：

http://en.wikipedia.org/wiki/Path_(computing)

归下类的话，有四种字符串：

1. "/"：为目录分隔符，用来分隔两个目录。

2. "."：当前目录

3. ".."：上层目录

4. 其他字符串：目录名

简化的核心是要找出所有的目录，并且如果遇到".."，需要删除上一个目录。

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

class Solution { public: string simplifyPath(string path) { string ret, curDir; vector<string> allDir; path.push_back('/'); for(int i=0; i<path.size(); i++) { if(path[i]=='/') { if(curDir.empty()) { continue; } else if(curDir==".") { curDir.clear(); } else if(curDir=="..") { if(!allDir.empty()) allDir.pop_back(); curDir.clear(); } else { allDir.push_back(curDir); curDir.clear(); } } else { curDir.push_back(path[i]); } } for(int i=0; i<allDir.size(); i++) ret.append("/"+allDir[i]); if(ret.empty()) ret = "/"; return ret; } };

[LeetCode] LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

思路：

LRU cache数据结构的核心就是当存储空间满了，而有新的item要插入时，要先丢弃最早更新的item。这里的数据结构需要符合以下条件：

1. 要能快速找到最早更新的item。这里需要将item以更新时间顺序排序。
可选的有：queue，heap，linked list

2. 要能快速访问指定item，并且访问以后要更新它的时间顺序。
对于更新时间顺序这个操作，queue和heap要做到就很困难了。所以这点最佳的是linked list。但linked list中查找指定item需要遍历，这里可以用一个hash table来记录key与节点之间的对应。并且由于要随时更新节点位置，doubly linked list更为适用。

根据以上两点，有了以下解法。注意由于代码较长，面试时尽可能将一些基本操作写成函数。

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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

class LRUCache{ struct Node { int val; int key; Node *next; Node *prev; Node(int k, int v):key(k),val(v) {} }; int maxSize; Node* head; Node* tail; unordered_map<int,Node*> keyToNode; void insertToEnd(int key, int value) { if(isFull() || keyToNode.count(key)!=0) return; Node *nd = new Node(key, value); keyToNode[key] = nd; if(!head) { head = tail = nd; } else { tail->next = nd; nd->prev = tail; tail = tail->next; } } void removeHead() { if(!head) return; keyToNode.erase(head->key); Node *temp = head; if(head==tail) // only one node remain head = tail = NULL; else { head = head->next; head->prev = NULL; } delete temp; } void moveToEnd(int key) { // key not exist, or already at the end if(keyToNode.count(key)==0 || keyToNode[key]==tail) return; Node *nd = keyToNode[key]; if(nd==head) { head = head->next; head->prev = NULL; } else { // not head, not tail nd->prev->next = nd->next; nd->next->prev = nd->prev; } tail->next = nd; nd->prev = tail; nd->next = NULL; tail = tail->next; } public: LRUCache(int capacity) { maxSize = capacity; head = NULL; tail = NULL; keyToNode.clear(); } int get(int key) { if(keyToNode.count(key)==0) return -1; moveToEnd(key); return keyToNode[key]->val; } void set(int key, int value) { // key already exists if(get(key)!=-1) { keyToNode[key]->val = value; return; } // key not exist, insert new node if(isFull()) removeHead(); insertToEnd(key, value); } bool isFull() { return keyToNode.size()>=maxSize; } };

[LeetCode] Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

思路：

从Insert Interval那题的解法，我们知道了如何判断两个interval是否重合，如果不重合，如何判断先后顺序。那么这题就很简单了，首先按照start的大小来给所有interval排序，start小的在前。然后扫描逐个插入结果。如果发现当前interval a和结果中最后一个插入的interval b不重合，则插入a到b的后面；反之如果重合，则将a合并到b中。注意要给object排序需要定义一个compare structure作为sort函数的额外参数。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: struct compInterval { bool operator()(const Interval &a, const Interval &b) const { return a.start<b.start; } }; vector<Interval> merge(vector<Interval> &intervals) { sort(intervals.begin(),intervals.end(),compInterval()); vector<Interval> ret; for(int i=0; i<intervals.size(); i++) { if(ret.empty() || ret.back().end < intervals[i].start) // no overlap ret.push_back(intervals[i]); else // overlap ret.back().end = max(ret.back().end, intervals[i].end); } return ret; } };

[LeetCode] Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

思路：

题目涉及两个问题：

1. 如何判断两个interval有重合。

2. 如果重合，如何合并。

3. 如何判断[s1, e1]是否在[s2, e2]前面

A1. 两个interval有重合有很多种可能性，但判断它们不重合则比较简单直观。无非两种情况：

(1) [s1, e1]  [s2, e2]：即s2>e1 

(2) [s2, e2]  [s1, e1]：即s1>e2

不重合的条件为：s2>e1 || s1>e2，反之则重合。

A2. 对于两个有重合的interval： [s1, e1]，[s2, e2]。合并后变为[min(s1,s2), max(e1,e2)]。

A3. [s1, e1]在[s2, e2]前面的条件：e1<s2

所以插入interval a的算法为：扫描队列中每个interval I[i]：
如果a已经被插入了，则只要插入I(i)就行。
如果a在I(i)前，则先插入a再插入I(i)到结果。

如果a和I(i)有重合，则将I(i)合并入a，但并不插入结果。

如果a在I(i)后，则插入I(i)到结果。

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

class Solution { public: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval> ret; bool isInsert = false; for(int i=0; i<intervals.size(); i++) { // already insert newInterval if(isInsert) { ret.push_back(intervals[i]); continue; } // insert newInterval before current interval if(newInterval.end < intervals[i].start) { ret.push_back(newInterval); ret.push_back(intervals[i]); isInsert = true; continue; } // combine newInterval with current interval if(newInterval.start<=intervals[i].end && intervals[i].start<=newInterval.end) { newInterval.start = min(newInterval.start, intervals[i].start); newInterval.end = max(newInterval.end, intervals[i].end); continue; } // newInterval after current interval ret.push_back(intervals[i]); } if(!isInsert) ret.push_back(newInterval); return ret; } };