寫CODE，會想到騎車也在想.....: LEET code -- Word Pattern

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Examples:

pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

我的作法是把patter都來做index 裡面放字串
如果再29行發現裡面字串不一樣就回傳失敗

還要檢查其他index有沒有一樣的字串(33行
因為可能 abba (dog dog dog dog)
ab都樣只靠29行是查不出來了

另外 17行要初始(這邊是給空的 == NULL)
另外不能使用memset 會失敗因為這裡是pointer char 不是char

最重要的字串比較不能用== 與!= 一定要strcmp
如果用== 與!= 他是比較兩個變數的base address記憶體位置不是內容
http://stackoverflow.com/questions/8004237/how-do-i-properly-compare-strings-in-c

在split中的第8行因為get 與ptr都是外面給的所以不會再回傳的時候消失

我覺得更好的演算法是最str中的字串當作index 而不是pattern
這邊有重複出現就知道了

但是要怎麼把一串字串轉成為一的int 是個麻煩

int split(char *ptr,char *symbo,char **get){//source, the symbo needto cut,useless size,return pointer
 int i=0;

 char *p=strtok(ptr,symbo);
 
 while(p!=0){
     //printf("%s ",p);
  *get++ = p;
        p = strtok(NULL,symbo);
        i++;
 }
 return i;
}

bool wordPattern(char* pattern, char* str) {
    //'A'=65   'a'=97
    char *table[26]={};//a array of 60 char* pointer, can't use memset to initial
    //memset(table,0,60);
    int strsize=strlen(str),patternsize=strlen(pattern);
    char *line[strsize];
    int lineSize=split(str," ",line);
    if(patternsize != lineSize)return false;
    for(int i=0;i<patternsize;i++){
        int index=(int)pattern[i] - 'a';
        if( table[ index ] == NULL){
            
            table[ index ] = line[i];
            printf("new %s %s \n",table[ (int)pattern[i] - 'a' ],line[i]);
        }else if(strcmp(table[ index ],line[i]) !=0){
            //printf("differ %s %s %d\n",table[ (int)pattern[i] - 'A' ],line[i]);
            return false;
        }
        for(int j=0;j<26;j++){
            if(j!=index &&table[j]!=NULL &&strcmp(table[index],table[j])==0)return false;
        }
    }
    return true;
    //printf("%d %d %s\n",patternsize,lineSize,line[0]);
}

--------------------------

直接利用while去找
利用hash去對每個字串做一個值直接判斷值有沒有依樣就好
最後回傳的時候要記得檢查 pattern 跟str有沒有都只到最後一個'\0'
沒有的話代表長度不一致

bool wordPattern(char* pattern, char* str) {
    //'A'=65   'a'=97
    int table[26];
    memset(table,0,sizeof(int)*26);
    
    for(;*pattern;pattern++){
        int index = (int)*pattern - 'a';
        while(*str && *str==' ')str++;
        char *te=str;
        int hash=0;
        while(*str && *str!=' '){
            hash =(11*hash+(int)*str);
            str++;
        }
       // printf("%d ",hash);
        if(table[ index ]==0){
            for(int j=0;j<26;j++){
                //check if other has the same value or not
                if(j!=index && table[j]==hash)return false;
            }
            table[index]=hash;
        }
        else if(table[index]!=hash)return false;
    }
    return !*pattern && !*str ;
    //return true only if both of the str and pattern are '\0'
}

寫CODE，會想到騎車也在想.....

2016年2月20日星期六

LEET code -- Word Pattern

沒有留言:

張貼留言

2016年2月20日 星期六

LEET code -- Word Pattern

沒有留言:

張貼留言

2016年2月20日星期六