Word Abbreviation

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

Valid Word Abbreviation

連結:https://leetcode.com/problems…

注意第一個數字是0的情況,[“a”, “01”]這種也是不合法的。

public class Solution {
public boolean validWordAbbreviation(String word, String abbr) {
/* while loop, i for word, j for abbr
* if it is number: count the number
* i  = number
* else: compare word.charAt(i) == abbr.charAt(j)
* end: i < len(word) && j < len(abbr)
* return i == len(word) && j == len(abbr)
*/
int i = 0, j = 0;
while(i < word.length() && j < abbr.length()) {
// character
if(abbr.charAt(j) > '9' || abbr.charAt(j) <= '0') {
// characters not same
if(word.charAt(i) != abbr.charAt(j)) return false;
i  ;  j  ;
}
// count number
else {
int count = 0;
while(j < abbr.length() && Character.isDigit(abbr.charAt(j))) {
count = 10 * count   (abbr.charAt(j) - '0');
j  ;
}
i  = count;
}
}
return i == word.length() && j == abbr.length();
}
}

        // if number: 
// if character: check the same
int i = 0;
int m = word.length(), n = abbr.length();
int count = 0;
for(int j = 0; j < abbr.length(); j  ) {
char c = abbr.charAt(j);
// number
if(c >= '0' && c <= '9') {
if(count == 0 && c == '0') return false;
count = count * 10   (c - '0');
}
// digit
else {
i  = count;
if(i >= word.length() || word.charAt(i) != c) return false;
count = 0;
i  ;
}
}
return i   count == m;

Minimum Unique Word Abbreviation

題目連結:https://leetcode.com/problems…

又是一道backtracking的題。看了這個部落格的解法:
http://bookshadow.com/weblog/…

現在是窮舉可能的結果,注意prune,然後check是否有和dict相同的。還有一個注意的就是要想和target有相同的縮寫,長度必須和它相同,所以dict只保留長度相同的。注意剪枝,當前長度已經超過globalMin就不需要繼續了。

public class Solution {
public String minAbbreviation(String target, String[] dictionary) {
// only keep the words has the same length
int len = target.length();
for(String s : dictionary) {
if(s.length() == len) dict.add(s);
}
// no word has the same length as target
if(dict.isEmpty()) return String.valueOf(target.length());
globalMin = len;
global = target;
dfs(target, 0, 0, "");
return global;
}
Set<String> dict = new HashSet();
int globalMin;
String global;
private void dfs(String target, int index, int len, String abbr) {
// pruning
if(len >= globalMin) return;
// base case
if(index == target.length()) {
for(String word : dict) {
if(validWordAbbreviation(word, abbr)) return;
}
globalMin = len;
global = abbr;
return;
}
// 2 subproblems:
// 1. target[i] = char 
// 2. target[i] = num
dfs(target, index   1, len   1, abbr   target.charAt(index));
int abbr_len = abbr.length();
if(index == 0 || !Character.isDigit(abbr.charAt(abbr_len - 1))) {
dfs(target, index   1, len   1, abbr   1);
}
else {
int num = 1   (abbr.charAt(abbr_len - 1) - '0');
dfs(target, index   1, len, abbr.substring(0, abbr_len-1)   num);
}
}
private boolean validWordAbbreviation(String word, String abbr) {
// if number: 
// if character: check the same
int i = 0;
int m = word.length(), n = abbr.length();
int count = 0;
for(int j = 0; j < abbr.length(); j  ) {
char c = abbr.charAt(j);
// number
if(c >= '0' && c <= '9') {
if(count == 0 && c == '0') return false;
count = count * 10   (c - '0');
}
// digit
else {
i  = count;
if(i >= word.length() || word.charAt(i) != c) return false;
count = 0;
i  ;
}
}
return i   count == m;
}
}

還有bit的方法,感覺好厲害!!完全沒想出來。
二進位制的做法是這樣的,先對字典裡面的單詞進行處理。一個char一個char處理,如果該char和target對應位置上的一樣,則記為1,否則記為0,這樣處理完之後就知道哪些位置上的字母可以換成數字。對target進行縮寫的時候,保留字母的記為1,換成數字的記為0,這樣查target的abbr是否是word的縮寫時,只需要把兩者相與看是否和abbr相同即可。
我還是沒搞懂這個到底是怎麼想出來的,明天再看看。

public class Solution {
public String minAbbreviation(String target, String[] dictionary) {
len = target.length();
globalMin = target.length() 1;
global = 0;
getBitDict(target, dictionary);
// edge case: target in dict, no word with same len
if(globalMin == 0) return target;
if(dict.size() == 0) return String.valueOf(len);
// backtracking
dfs(0, 0, 0);
return bitToString(target);
}
List<Integer> dict = new ArrayList();
int globalMin;
int global;
int len;
private void dfs(int index, int curLen, int abbr) {
// prune
if(curLen >= globalMin) return;
// base case
if(index == len) {
for(int word : dict) {
if((word & abbr) == abbr) return;
}
globalMin = curLen;
global = abbr;
return;
}
// 1. character
dfs(index   1, curLen   1, (abbr << 1)   1);
// 2. number
if(index == 0 || (abbr%2) == 1) dfs(index   1, curLen   1, (abbr << 1));
else dfs(index   1, curLen, (abbr << 1));
}
private void getBitDict(String target, String[] dictionary) {
// bit: 1. s[i] == target[i] => 1
//      2. s[i] != target[i] => 0
int len = target.length();
for(String s : dictionary) {
if(s.length() == len) {
// edge case
if(s.equals(target)) {
globalMin = 0;
return;
}
int bitString = 0;
for(int i = 0; i < len; i  ) {
bitString = bitString << 1;
if(target.charAt(i) == s.charAt(i)) bitString  = 1;
}
dict.add(bitString);
}
}
}
private String bitToString(String target) {
String result = "";
int count = 0;
for(int i = 0; i < len; i  ) {
if(((global >> len - i - 1) & 1) == 1) {
if(count != 0) result  = count;
count = 0;
result  = target.charAt(i);
}
else count  ;
}
if(count != 0) result  = count;
return result;
}
}

練習白板第一天,板子買小了。思路寫的也不整齊,擦了好幾次,大概寫了30分鐘,還需要多多練習額。。dfs的題,下次寫的時候,還是按照start -> arguments&return type -> base case -> subproblem的順序來,pruning最後添上。明天研究性下怎麼寫時間複雜度的。
clipboard.png

相關文章

程式語言 最新文章