首页 > 试题广场 >

单词消消乐

[编程题]单词消消乐
  • 热度指数:3690 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
"一清二白,白头偕老,老当益壮.....",牛牛和牛妹在玩成语接龙,但是牛妹因为语文不好总是输,于是她想出了一个新的游戏去和牛牛玩,牛妹会给牛牛n个单词,牛妹要求牛牛将这n个单词按照以下方式合并:

1.从左往右合并单词,将合并后的单词作为第一个单词再与后面单词合并
例如有三个单词"a","b","c",先将"ab"合并,最后将合并后的"ab"与"c"合并得到"abc"。
2.如果最左边单词结尾字母与其后面一个的单词的开始字母相同,则最左边单词的结尾字母与之后一个单词的开始字母都会抵消掉而消失,重复上述操作直到某一个单词为空或者最左端的结尾字母与之后单词的开始字母不同,然后合并这两个单词作为一个单词放置再最左边。

例如 "aab" "bac"合并之后会得到"ac"


返回最终合并后的单词。
若为空则返回一个空串。
示例1

输入

["aab","bac","ccd"]

输出

"acd"

说明

"aab"与"bac"合并得到"ac"
"ac"再与"ccd"合并得到"acd"

备注:
string数组 的形式给定n个单词
  
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param Words string字符串一维数组 
     * @return string字符串
     */
    public String WordsMerge (String[] Words) {
        // write code here
        if(Words.length==0){
            return "";
        }
        String str="";
        Queue<Character> qe=new LinkedList<>();
        Queue<Character> qe1=new LinkedList<>();
        for(String str1:Words){
            if(str==null){
                str=str1;
            }else if(str1==null){
                continue;
            }else{
                while(str.length()>0&&str.charAt(str.length()-1)==str1.charAt(0)){
                    str=str.substring(0,str.length()-1);
                    str1=str1.substring(1,str1.length());
                }
                str=str+str1;
            }
        }
        return str;
    }
}
发表于 2021-07-16 10:47:44 回复(0)
有点坑。。注意如果下一个单词头一个字母和第一个单词最后一个字母不相同,就直接把后一个单词接在当前结果后面,不要一个一个字母地接,否则就会导致后一个单词中相同且连续的字母消掉..
class Solution {
public:
    /**
     *
     * @param Words string字符串vector
     * @return string字符串
     */
    string WordsMerge(vector<string>& Words) {
        // write code here
        int len = 0, n = Words.size();
        for(int i=0;i<n;i++) len+=Words[i].size();
        char* res = new char[len+1];
        int cnt = Words[0].size();
        for(int i=0;i<cnt;i++) res[i] = Words[0][i];
        for(int i=1;i<n;i++){
            string cur = Words[i];
            int cl = cur.size();
            for(int j=0;j<cl;j++){
                if(cnt&&res[cnt-1]==cur[j]) cnt--;
                else{
                    while(j<cl) res[cnt++] = cur[j++];
                    break;
                }
            }
        }
        res[cnt] = '\0';
        string r(res);
        delete[] res;
        return r;
    }
};

发表于 2020-03-31 14:30:08 回复(0)
class Solution {
public:
    /**
     * 
     * @param Words string字符串vector 
     * @return string字符串
     */
    string WordsMerge(vector<string>& Words) {
        string t = Words[0];
        for(int i=1;i<Words.size();i++){
            for(int j=0;j<Words[i].length();j++){
                if(!t.empty() && t.back() == Words[i][j])
                    t.pop_back();
                else{
                    t += Words[i].substr(j);
                    break;
                }
            }
        }
        return t;
    }
};

发表于 2020-07-01 00:16:20 回复(0)
char* WordsMerge(char** Words, int WordsLen ) {
    // write code here
     char *pStr1 = (char *)malloc(1000);
     char *pStr = pStr1;
    unsigned char i = 0;
    unsigned char j = 0;
    for(i = 0; i < WordsLen; i++)
    {
        for(j = 0; *(*(Words + i) + j); j++)
        {
            if(i >= 1)
            {
                if(*pStr == *(*(Words + i) + j))
                {
                    *pStr = '\0';
                    pStr--;
                    continue;
                }
                else
                {
                    pStr++;
                }
            }
            *pStr = *(*(Words + i) + j);
            if(*(*(Words + i) + j + 1))
            {
                pStr++;
            }
        }
    }
    return pStr1;
}

发表于 2022-03-10 22:32:07 回复(0)
function WordsMerge(Words) {
    // write code here
    if (Words.length < 2) {
        return Words.toString();
    }
    let str = "";
    // 将第一个翻转,删除公共前缀
    let str1 = Words[0].split("").reverse().join("");
    let str2 = Words[1];
    for (let i = 0; i < str1.length; i++) {
        if (i === str2.length || str2.charAt(i) !== str1[i]) {
            str =
                str1.slice(i).split("").reverse().join("") + str2.slice(i) + "";
            break;
        }
    }
    Words.splice(0, 2, str);
    return WordsMerge(Words);
}

发表于 2023-09-22 13:16:32 回复(0)
class Solution:
def WordsMerge(self , Words ):
# write code here
res = ''
for w in Words:
while res != '' and w != '' and res[-1] == w[0]:
res = res[:-1]
w = w[1:]
res += w
return res
发表于 2023-06-23 14:59:24 回复(0)
class Solution:
    def WordsMerge(self , Words ):
        # write code here
        s = list()
        for word in Words:
            for w in word:
                if not s or s[-1] != w:
                    s.append(w)
                else:
                    s.pop()
        return ''.join(s)
发表于 2022-06-02 16:23:28 回复(0)

/**
       * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
       *
       *
       * @param Words string字符串一维数组
       * @return string字符串
       */
      function WordsMerge(Words) {
        // write code here
        if (!Words.length) {
          return "";
        }

        // 定义一个字符串模拟栈操作
        let str = "";

        str = Words[0];
        if (Words.length === 1) {
          return str;
        }

        for (let i = 1; i < Words.length; i++) {
          let temp = Words[i];
          for (let j = 0; j < temp.length; j++) {
            const start = temp[j];
            const end = str.slice(str.length - 1, str.length);
            // 最后等与开始
            // 截取最后的元素
            if (end === start) {
              str = str.slice(0, str.length - 1);
            } else {
              // 不相等直接拼接上去
              str = str.concat(temp.slice(j, temp.length));
              break;
            }
          }
        }
        return str;
      }

发表于 2022-04-12 17:03:06 回复(0)
# 没有看到,附上Python解法,希望有帮助
class Solution: def WordsMerge(self , Words ):
        items = [] tp = 0  for i in range(len(Words[0])):#准备初试的栈  items.append(Words[0][i]) # print(items)  for i in range(1,len(Words)): for j in range(len(Words[i])): #顺序查找当前Word[i][j]  if Words[i][j] in items: # pop 相同元素(找到下标)  for v in range(len(items)): # print(Words[i][j],v,items)  if Words[i][j] == items[v]: tp = v
                    items.pop(v) else:
                    items.append(Words[i][j])
        li = "".join(items) print(li) return li

发表于 2021-09-01 11:43:25 回复(0)
import java.util.*;
public class Solution {
    public String WordsMerge (String[] Words) {
        // write code here
        String str="";
        String res="";
        for (int i=0;i<Words.length;i++){
            str=str+Words[i];
        }
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==str.charAt(i+1)){
                i++;
            }else{
                res=res+str.charAt(i);
            }
        }
        return res;
    }
}

发表于 2021-08-03 20:43:41 回复(0)
public String WordsMerge (String[] Words) {
        // write code here
        if(Words == null || Words.length == 0) {
            return "";
        }
        if(Words.length == 1) {
            return Words[0];
        }
        
        Deque<Character> stack = new ArrayDeque<> ();
        String firstWord = Words[0];
        for(int i = 0; i < firstWord.length(); i++) {
            stack.push(firstWord.charAt(i));
        }
        
        for(int i = 1; i < Words.length; i++) {
            String curWord = Words[i];
            char firChar = curWord.charAt(0);

            if(firChar != stack.peek()) {
                for(int j = 0; j < curWord.length(); j++) {
                    stack.push(curWord.charAt(j));
                }
            } else {
                for(int k = 0; k <curWord.length(); k++) {
                    char temp = curWord.charAt(k);
                    if(temp == stack.peek()){
                        stack.pop();
                    } else {
                        break;
                    }
                }
                for(int kk = 0; kk <curWord.length(); kk++) {
                    stack.push(curWord.charAt(kk));
                }
            }   
        }
        
        StringBuilder SB = new StringBuilder();
        while(!stack.isEmpty()){
            SB.insert(0, stack.pop());
        }
        String res = SB.toString();
        return res; 
    }
这么写,会报错时间复杂度过高,但应该是O(n^2),不知道哪里还可以优化呢?
发表于 2020-09-25 23:36:27 回复(0)
93%通过率,为啥呀

function WordsMerge(Words) {
  // write code here
  let stack = [];

  // 先让第一个单词入栈
  for (let i = 0; i < Words[0].length; i++) {
    stack.push({
      letter: Words[0][i],
      flag: 0
    });
  }

  for (let i = 1; i < Words.length; i++) {
    let word = Words[i]
    for (let j = 0; j < word.length; j++) {
      const ch = word[j];
      const last = stack[stack.length - 1];
      if (last.letter === ch && last.flag !== i) {
        stack.pop()
      } else {
        stack.push({
          letter: ch,
          flag: i
        })
      }
    }
  }
  var strarr = stack.map((item) => item.letter)
  return strarr.join('')
}

module.exports = {
  WordsMerge: WordsMerge
};



发表于 2020-08-19 15:15:32 回复(0)
function WordsMerge(Words) {
            // write code here
            let output = '';
            let startStr = Words[0];
            for (let i = 1i < Words.lengthi++) {
                let endIndexNum = 0;
                for (let j = startStr.length - 1j >= 0j--) {
                    if (startStr[j] == Words[i][endIndexNum]) {
                        endIndexNum++
                    }
                }
                startStr = [startStr.slice(0startStr.length - endIndexNum) + Words[i].slice(endIndexNumWords[i].length)][0];
            }
            return startStr
        }
        alert(WordsMerge(["aab","bac","ccd"]));
        //此处打印出 "acd"  但是通过率只有6.67%
发表于 2020-08-13 15:04:06 回复(0)
class Solution {
public:
    /**
     * 
     * @param Words string字符串vector 
     * @return string字符串
     */
    //先用栈去理解算法过程,因为栈不能底部开始输出,所以采用了双端队列
    string WordsMerge(vector<string>& Words) {
        // write code here
        int i;
        int j;
        deque<char> re; //用双端队列
        int n = Words.size();
        int m;
        
        if (n <= 0)
            return NULL;
        re.push_back('#');
        for (i = 0; i < n; i++)
        {
            m = Words[i].size();
            for (j = 0; j < m; j++)
            {
                if (Words[i][j] == re.back())
                {
                    re.pop_back();
                }
                else   //尾 首不等就停止
                {
                   break;
                }
            }
            //把剩下的全部进栈中   
            for (; j < m; j++)
            {
                re.push_back(Words[i][j]);
            }
        }

        //队列元素按顺序出队  放到string中
        m = re.size() - 1;
        re.pop_front(); //把'#'弹掉
        string result(m + 1, '\0');  //‘\0’不要忘了  所以要多一个
        for (i = 0; i < m; i++)
        {
            result[i] = re.front();
            re.pop_front();
        }
        
        return result;
    }
};
发表于 2020-07-25 13:35:24 回复(0)
class Solution {
public:
    /**
     *
     * @param Words string字符串vector
     * @return string字符串
     */
    string WordsMerge(vector<string>& Words) {
        // write code here
        stack<char> s;
        int len=Words.size();
        string str_0=Words[0];
        //string t;                   //第一个字符串压栈
        for(int i=0;i<str_0.length();i++){
            s.push(str_0[i]);
            //t+=str_0[i];
        }
        int count=1;
        while(count<len){          //处理
            int flag=1;
            string str=Words[count];
            for(int j=0;j<str.length();j++){
                char c=str[j];
                if(c==s.top()&&flag==1){
                    s.pop();
                }else{
                    flag=0;
                    s.push(c);
                }
            }
            count++;
        }
        string temp,res;         //对栈输出
        while(!s.empty()){
            temp+=s.top();
            s.pop();
        }
        for(int i=temp.length()-1;i>=0;i--){
            res+=temp[i];
        }
        return res;
    }
};

//注意s.empty()和s.zise()的区别,开始我用的for(int i=0;i<s.size();i++)进行s.pop()操作得到的结果是错误的,,,
发表于 2020-07-21 14:49:32 回复(0)
#include <vector>
using namespace::std;
class Solution {
public:
    string WordsMerge(vector<string>& Words) {
        string s;
        s=Words[0];
        for(int i =1;i<Words.size();++i){
            for(int j=0;j<Words[i].length();++j){
                if(s.empty()){
                    s.append(Words[i].substr(j));
                    break;
                }
                else{
                    if(s.back() !=Words[i][j]){
                        s.append(Words[i].substr(j));
                        break;
                    }
                    else 
                        s.pop_back();
                }
            }
        }
        return s;
    }
};

发表于 2020-06-09 20:33:20 回复(1)