Day 49, #127, #131, Word Ladder, Palindrome Partitioning

Word Ladder
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.

------------------------------------------------------------------------
typical BFS and shortest path

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (start == end) return 1;
        queue<pair<string,int> > q;
        q.push(make_pair(start, 1)); // assign each node a distance
        unordered_set<string> used;
        while (!q.empty()) {
            string top = q.front().first;
            int length = q.front().second;
            q.pop();
            for (int index = 0; index < start.length(); index++ ) {
                for (int alp = 'a'; alp < 'z'; alp++) {
                    if (alp == top[index]) continue; // ignore the same letter
                    string temp = top;
                    temp[index] = alp;
                    if (temp == end) {
                        return length+1;
                    }
                    if (used.find(temp) == used.end() && dict.find(temp) != dict.end()) {
                        used.insert(temp);
                        q.push(make_pair(temp, length+1));
                    }
                    
                }
            }
        }
        return 0;
    }
};

Java,双向BFS, udpated on Aug-4th-2018

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int len = 1;
        Map<String, Boolean> dic = getDic(wordList);
        if (!dic.containsKey(endWord)) return 0;
        
        dic.put(beginWord, false);
        dic.put(endWord, false);
        Set<String> begin = new HashSet<>();
        Set<String> end = new HashSet<>();
        begin.add(beginWord);
        end.add(endWord);
        
        while (!begin.isEmpty() && !end.isEmpty()) {
            if (begin.size() > end.size()) {
                Set<String> t = begin;
                begin = end;
                end = t;
            }
            
            len++;
            Set<String> temp = new HashSet<>();
            for (String s : begin) {
                for (int i = 0; i < s.length(); i++) {
                    char c = s.charAt(i);
                    for (char nextC = 'a'; nextC <= 'z'; nextC++) {
                        String next = s.substring(0, i) + nextC + s.substring(i + 1);

                        if (end.contains(next)) return len;

                        if (dic.containsKey(next) && dic.get(next)) {
                            temp.add(next);
                            dic.put(next, false);
                        }
                    }
                }
            }
            
            begin = temp;
        }
        
        return 0;
    }
    
    private Map<String, Boolean> getDic(List<String> wordList) {
        Map<String, Boolean> dic = new HashMap<>();
        
        for (String s : wordList) {
            dic.put(s, true);
        }
        
        return dic;
    }
}

Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

-----------------------------------------
DFS, recursive

class Solution {
public:
    bool checkPalin (string s) {
        for (int i = 0; i < s.length()/2; i++) {
            int end = s.length() - 1 - i;
            if (s[i] != s[end]) {
                return false;
            }
        }
        return true;
    }
    
    void partition (string cur, vector<string> v, string remain,  vector<vector<string> >& ret) {
        if (remain.empty()) {
            ret.push_back(v);
            return;
        }
        
        for (int i = 0; i < remain.length(); i++) {
            cur += remain[i];
            if (checkPalin(cur)) {
                vector<string> cp = v; 
                cp.push_back(cur);
                partition("",cp,remain.substr(i+1),ret);
            }
        }
    }
    
    vector<vector<string>> partition(string s) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        vector<vector<string> > ret;
        vector<string> v;
        partition("",v,s,ret);
        return ret;
    }
};

Update on Oct-03-2014
Using index

class Solution {
public:
    bool isPal(string str) {
        for (int i = 0; i < str.length() / 2; i++) {
            if (str[i] != str[str.length() - 1 - i]) {
                return false;
            }
        }
        
        return true;
    }
    
    void dfs(vector<vector<string> > &rt, vector<string> cur, string s,int index) {
        if (index == s.length()) {
            rt.push_back(cur);
            return;
        }
        for (int i = 1; i < s.length() - index + 1; i++) {
            string sub = s.substr(index,i);    
            if (isPal(sub)) {
                vector<string> temp = cur;
                temp.push_back(sub);
                dfs(rt,temp,s,index + i);
            }
        }
    
    }
    
    vector<vector<string>> partition(string s) {
        vector<vector<string> > rt;
        vector<string> v;
        dfs(rt,v,s,0);
        return rt;
    }
};

Thoughts: we can add Memoization to improve efficiency. Set up a 2d-array of vector<vector<string> >, [i][j] contains all palindrome partitionings between i and j